Two Pointer Approach in Python

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]