# 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

FAANGinterviews: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 Pointersapproach.

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:

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

- Search for ‘Y’ (which is equivalent to “
**Target - X**”) in the**HashTable**. If it is there, we have found the required pair. - 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 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];}

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