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
Solution
Visualization
Python
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.
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
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.