Two Pointers : Pattern for Coding Questions

Hack the coding interviews at FAANG!

In problems where we deal with sorted arrays (or LinkedLists) and need to find a set of elements that fulfill certain constraints, the Two Pointers approach becomes quite useful. The set of elements could be a pair, a triplet or even a subarray.

Question at FAANG interviews: Pair with Target Sum

Problem Statement : Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

Write a function to return the indices of the two numbers (i.e. the pair) such that they add up to the given target.

Example :

Input: arr = [1, 2, 3, 4, 6], target=6
Output: [1, 3]
Explanation: The numbers at indices 1 and 3 add up to 6: 2+4=6

Solution 1 : We can follow the Two Pointers approach.

We will start with one pointer pointing to the beginning of the array and another pointing at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do, we have found our pair; otherwise, we will do one of two things:

1. If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
2. If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Here is the visual representation of this algorithm for Example:

Code (JavaScript)

function pair_with_target_sum(arr, targetSum) {
let left = 0,
right = arr.length - 1;
while (left < right) {
const currentSum = arr[left] + arr[right];
if (currentSum === targetSum) {
return [left, right];
}

if (targetSum > currentSum) {
left += 1; // we need a pair with a bigger sum
} else {
right -= 1; // we need a pair with a smaller sum
}
}
return [-1, -1];
}

Time Complexity

The time complexity of the above algorithm will be O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The algorithm runs in constant space O(1).

Solution 2 : using HashTable

Instead of using a two-pointer, we can utilize a HashTable to search for the required pair. We can iterate through the array one number at a time. Let’s say during our iteration we are at number ‘X’, so we need to find ‘Y’ such that “X + Y = Target”. We will do two things here:

1. Search for ‘Y’ (which is equivalent to “Target - X”) in the HashTable. If it is there, we have found the required pair.
2. Otherwise, insert “X” in the HashTable, so that we can search it for the later numbers.

Code (JS)

function pair_with_target_sum(arr, targetSum) {
const nums = {}; // HashTable to store numbers and their indices
for (let i = 0; i < arr.length; i++) {
const num = arr[i];
if (targetSum - num in nums) {
return [nums[targetSum - num], i];
}
nums[arr[i]] = i;
}
return [-1, -1];
}

Time Complexity

The time complexity of the above algorithm will be O(N), where ’N’ is the total number of elements in the given array.

Space Complexity

The space complexity will also be O(N), as, in the worst case, we will be pushing ’N’ numbers in the HashTable.

That’s all for Pattern — Two Pointers. Will discuss more patterns for coding interview questions in the upcoming stories.