Two Pointers
Two Sum (Sorted Array)
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Given a sorted array of integers nums, determine if there exists a pair of numbers that sum to a given target.
Example 1:
Input:
nums = [1,3,4,6,8,10,13] target = 13
Output:
True # (3 + 10 = 13)
Example 2:
Input:
nums = [1,3,4,6,8,10,13] target = 6
Output:
False
Constraints:
- nums may be empty or hold a single element, so nums.length can be less than 2.
- nums is sorted in non-decreasing order.
- Every value in nums and target fits in a 32-bit signed integer.
Solution
Visualization
Try these examples:
def twoSum(nums, target):left, right = 0, len(nums) - 1while left < right:current_sum = nums[left] + nums[right]if current_sum == target:return Trueif current_sum < target:left += 1else:right -= 1return False
two sum algorithm
0 / 7
Explanation
Because the input is sorted, we can solve this question in O(n) time and O(1) space using the two-pointer technique by eliminating unnecessary pairs from our search.
Let's say we want to find a pair of numbers that sum to 13 in the following array:
We start by initializing two pointers at opposite ends of the array, which represent the pair of numbers we are currently considering. Note that this pair has a sum (14) that is greater than our target (13). Starting at opposite ends lets us efficiently adjust: moving left right increases the sum, while moving right left decreases it.
Because our array is sorted, all other pairs using 13 (the element at our right pointer) also have sums greater than our target, as they all use numbers greater than 1 (the element at our left pointer).
So, we move our right pointer back, which elimininates those unnecessary pairs from our search, and arrive at the next pair to consider.
Now, since our sum is less than our target, we know that all other pairs using 1 also have sums less than our target. So, we move our left pointer forward to eliminate those unnecessary pairs and arrive at the next pair to consider.
This continues until either our pointers meet (in which case we did not find a successful pair) or until we find a pair that sums to our target, like we did here.
Complexity
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) where n is the length of the input array. The two pointers start at opposite ends and only ever move toward each other, so each element is visited at most once before the pointers meet. We do constant work at every step, which adds up to a single linear pass.
Space Complexity: O(1) we only keep the two pointer indices around. No matter how large the input gets, the extra memory we use stays fixed.
Summary
- We initialize our two pointers at opposite ends of the array, and start our search.
- If the sum of the current pair is greater than our target, we move our right pointer back. If it is less than our target, we move our left pointer forward.
- Each time we move a pointer, we eliminate unnecessary pairs from our search.
- We continue this process until either our pointers meet or until we find a pair that sums to our target.
- While this question is on the easier side for many coding interviews, it's a key step in harder questions such as 3Sum and 3Sum closest, which start by sorting an unsorted array in order to use the two-pointer technique described here.
Mark as read
Your account is free and you can post anonymously if you choose.