Assume that you are given a task to find a pair in an array that sums to S. Whenever I encounter problems around this line, the first approach that I can think of is the Two-pointer approach. The reason behind that is it’s super easy to understand and implement.
How sorted array work?
In a sorted array, if you want to find a pair satisfying some condition you can use this approach as at each step we know how to update the pointers.
For better understanding, let’s take an example. Suppose we have an array ‘arr’ and we want to find a pair from it that sums to a ‘target’.
Example. arr = [-4, 1, 2, 4, 5, 9], target = 7
Step 1. Initializing two pointers
We’ll start with initializing our two pointers, let’s name them ‘low’ and ‘high’.
- low: this pointer will point to the index of the smallest element, in a sorted array it will be the first element of the array.
- high: this pointer will point to the index of the greatest element, in a sorted array it will be the last element of the array.
low = 0
high = len(arr) - 1 # as python follows 0-indexing
Step 2. Check elements at both pointers
At each step, we will check if the elements at both pointers are equal to the target or satisfy the condition or not. There are 3 possible outcomes:
result = arr[low] + arr[high]
2.1 result < target
In this case, we need a larger element to come close to the target. For this obviously, we’ll update the pointer which was pointing to the smaller element i.e., “low”.
if result < target:
left += 1
2.2 result > target
In this case, we need a smaller element to come close to the target. Using the above logic, you can definitely think that this time we’ll update the pointer pointing to a larger element i.e., “high”.
if result > target:
right -= 1
2.3 result == target
Voila, you got the pair.
Use Case
Question URL: https://leetcode.com/problems/two-sum/
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for index, num in enumerate(nums):
remainder = target - num
if remainder not in seen:
seen[num] = index
else:
return [seen[remainder], index]