Two Pointers : Pattern for Coding Questions

Hack the coding interviews at FAANG!

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
  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.

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).

  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.
function pair_with_target_sum(arr, targetSum) {const nums = {}; // HashTable to store numbers and their indicesfor (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];}

--

--

Web Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store