👨‍💻
LeetCode
  • Overview
  • Mixed / Design
    • Two Sum (4 Qs)
      • 0001. Two Sum
      • 0167. Two Sum II - Input array is sorted
      • 0170. Two Sum III - Data structure design
      • 0653. Two Sum IV - Input is a BST
    • 0015. 3Sum
    • 0208. Implement Trie (Prefix Tree)
  • String
    • 0014. Longest Common Prefix
    • 0028. Implement strStr()
    • 0344. Reverse String
    • 0151. Reverse Words in a String
    • 0557. Reverse Words in a String III
    • 0067. Add Binary
    • 0415. Add Strings
    • 0038. Count and Say
    • 0394. Decode String
    • 0953. Verifying an Alien Dictionary
    • 0020. Valid Parentheses
  • Linked List
    • 0002. Add Two Numbers
    • 0445. Add Two Numbers II
    • 0021. Merge Two Sorted Lists
    • 0023. Merge k Sorted Lists
    • 0206. Reverse Linked List
    • 0019. Remove Nth Node From End of List
  • Tree
    • 0098. Validate BST
    • 0100. Same Tree
    • 0101. Symmetric Tree
    • 0226. Invert Binary Tree
    • 0110. Balanced Binary Tree
    • 0250. Count Univalue Subtrees
    • 0654. Maximum Binary Tree
    • Binary Tree Traversal (7 Qs)
      • 0144. Preorder Traversal
      • 0145. Postorder Traversal
      • 0094. Inorder Traversal
      • 0102. Level Order Traversal
      • 0104. Maximum Depth
      • 0111. Minimum Depth
      • 1302. Deepest Leaves Sum
      • 0993. Cousins in Binary Tree
    • N-ary Tree Traversal (4 Qs)
      • 0589. Preorder Traversal
      • 0590. Postorder Traversal
      • 0429. Level Order Traversal
      • 0559. Maximum Depth
    • Convert to BST (2 Qs)
      • 0108. Convert Sorted Array to Binary Search Tree
      • 0109. Convert Sorted List to Binary Search Tree
  • Binary Search
    • 0704. Binary Search
    • 0035. Search Insert Position
    • 0278. First Bad Version
    • 0367. Valid Perfect Square
    • 0069. Sqrt(x)
    • 0875. Koko Eating Bananas
    • 1011. Capacity To Ship Packages Within D Days
    • 0410. Split Array Largest Sum
    • 0004. Median of Two Sorted Arrays
  • Two Pointer
    • 0075. Sort Colors
    • 0088. Merge Sorted Array
    • 0283. Move Zeroes
    • 0125. Valid Palindrome
    • 0011. Container With Most Water
    • 0026. Remove Duplicates from Sorted Array
  • Sliding Window
    • 0003. Longest Substring Without Repeating Characters
  • Sorting
    • 0148. Sort List
    • 0912. Sort an Array
    • 0215. Kth Largest in Array
  • Dynamic Programming
    • 0509. Fibonacci Number
    • 1137. N-th Tribonacci Number
    • 0055. Jump Game
    • 0053. Maximum Subarray
    • 0022. Generate Parentheses
    • 0005. Longest Palindromic Substring
    • 0072. Edit Distance
    • Buy and Sell Stock (6 Qs)
      • 0122. Best Time to Buy and Sell Stock II
      • 0714. Best Time to Buy and Sell Stock with Transaction Fee
      • 0121. Best Time to Buy and Sell Stock
      • 0309. Best Time to Buy and Sell Stock with Cooldown
      • 0123. Best Time to Buy and Sell Stock III
      • 0188. Best Time to Buy and Sell Stock IV
  • DFS / BFS
    • 0200. Number of Islands
  • Math
    • 0007. Reverse Integer
    • 0009. Palindrome Number
Powered by GitBook
On this page

Was this helpful?

  1. Mixed / Design
  2. Two Sum (4 Qs)

0167. Two Sum II - Input array is sorted

Easy | Two Pointer | 56 ms (95.70%), 14.8 MB (32.12%)

Previous0001. Two SumNext0170. Two Sum III - Data structure design

Last updated 3 years ago

Was this helpful?

Source: GitHub:

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Constraints:

  • 2 <= numbers.length <= 3 * 104

  • -1000 <= numbers[i] <= 1000

  • numbers is sorted in non-decreasing order.

  • -1000 <= target <= 1000

  • The tests are generated such that there is exactly one solution.

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Input: numbers = [-1,0], target = -1
Output: [1,2]

Since there is exactly one solution, two-pointers with dynamically adjusted indexes could help to solve.

Starting with the left- and right-most elements, we sum up them to see whether the result meets the target value.

  • If the result is greater than the target, we move the right-pointer forward.

  • If the result is less than the target, we move the left-pointer backward.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # (base case)
        if len(numbers) == 2: return [1, 2] if sum(numbers) == target else [-1, -1]
        
        # ==================================================
        #  Array + Two Pointer                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        l, r = 0, len(numbers) - 1
        while l < r:
            tmp = numbers[l] + numbers[r]
            if   tmp == target: return [l+1, r+1]
            elif tmp > target: r -= 1
            elif tmp < target: l += 1
                
        return [-1, -1]
        
        '''
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        for i in range(len(numbers) - 1):
            l = i + 1
            r = len(numbers) - 1
            remain = target - numbers[i]
            
            while l <= r:
                mid = (l + r) // 2
                if   numbers[mid] == remain: return [i+1, mid+1]
                elif numbers[mid]  > remain: r = mid - 1
                elif numbers[mid]  < remain: l = mid + 1
                    
        return [-1, -1]
        '''
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(1)
     */
    
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        
        while(l < r) {
            int tmp = numbers[l] + numbers[r];
            if(tmp == target) return new int[] {l+1, r+1};
            else if(tmp > target) r--;
            else if(tmp < target) l++;
        }
        
        return new int[] {-1, -1};
    }
}
LeetCode - Two Sum II - Input array is sorted
Solution / Performance