Two Pointers

In this chapter you will learn the basics of Two Pointers technique and how to apply it in a different problems.

The Two Pointers technique is a simple and effective way to solve problems that deal with searching for a pair in a sorted array, or a subarray in a sorted array, etc.

The technique uses two pointers that move through the array at different speeds, depending on the problem.

Problem

Given a sorted array of integers, write a function that returns the indices of the two numbers that add up to a specific target.

If no such pair exists, return null.

Example

let arr = [2, 7, 11, 15];
let target = 9;

console.log(twoSum(arr, target)); // [0, 1]

Solution

Algorithm

To solve this problem, we will use a two pointers algorithm:

• Initialize a two pointers: left pointing to the start of the array (index 0), and right pointing to the end of the array (index arr.length - 1)
• Enter a loop that continues while left is less than right
• Calculate the sum of the elements at left and right indices: sum = arr[left] + arr[right]
• Compare the sum with the target:
  • If sum equals target, return the result [left, right]
  • If sum is less than target, increment left pointer by 1 (move forward larger values)
  • If sum is greater than target, decrement right pointer by 1 (move forward smaller values)
• If loop completes without finding a solution, return null

Implementation

function twoSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    let sum = arr[left] + arr[right];

    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

Complexity Analysis

• The time complexity of the Two Pointers technique is O(n) where n is the number of elements in the array.
• The space complexity is O(1) since we are using only a constant amount of space.

Practice

• Reverse String: Write a function that reverses a string. The input string is given as an array of characters.
• Valid Palindrome: Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
• Remove Duplicates from Sorted Array: Given a sorted array, remove the duplicates in-place such that each element appears only once and return the new length.