Data Structure and Algorithm
Coding Patterns
Two Pointers

Two Pointer Technique

The Two Pointer method is a way to solve problems using two variables (called "pointers") that move through a list or array. It helps us write faster and cleaner code.


πŸ“Œ Why Two Pointers?

The Two Pointer technique is used to solve problems faster and using less memory. Instead of checking every possible pair or combination, we use two variables (pointers) to move smartly and find the answer.


πŸ“˜ What is the Pattern?

  • Use two variables (pointers).
  • Place them at different positions depending on the problem:
    • One at the start and one at the end.
    • Both at the start, moving in the same direction.
    • One on each array, moving in parallel.
  • Move the pointers based on the logic until a condition is met.

πŸš€ Why Use Two Pointers?

  • Speeds up the solution (from O(n^2) to O(n)).
  • Uses less memory.
  • Makes code shorter and cleaner.
  • Works great with sorted arrays, strings, and linked lists.
  • When you need to find pairs, triplets, or subarrays meeting certain conditions.
  • When the data is sorted or can be sorted.
  • When you want to optimize brute force solutions that use nested loops O(n^2) to linear or near-linear time O(n).

How It Works?

You maintain two pointers that move through the data structure according to certain rules:

  • One pointer starts at the beginning, the other at the end (common in problems like finding pairs with a sum).
  • Or, both pointers start at the beginning, with one moving faster than the other (useful for sliding window problems).
  • Move pointers towards each other or forward depending on the problem condition.

πŸ•΅οΈβ€β™‚οΈ When Do We Use It?

Use Two Pointers when:

  • You're working with a sorted or unsorted array, string, or linked list.
  • You need to find pairs, check for conditions (like sum, duplicates, palindromes).
  • You're solving problems with subarrays, substrings, or ranges.
  • You're trying to reverse, compare, or merge two structures.
  • You need to traverse at different speeds (e.g., slow & fast pointers in linked lists).

Typical Approach:

  • Initialize two pointers, left and right.
  • Check condition based on the current pointers.
  • Move pointers accordingly:
    • If condition not met, move left or right pointer to try to satisfy the condition.
    • If condition met, record the answer or move pointers to find more solutions.
  • Repeat until pointers cross or reach the end.

πŸ” Recognizing a Two-Pointer Problem

Ask yourself:

  • Can I solve this by checking from both ends?
  • Am I looking for pairs, ranges, or merging?
  • Can I move two variables instead of using extra space?

If yes, then Two Pointer is probably the right choice!


🧠 Where to Use Two Pointers?

You can use this pattern with:

  • βœ… Arrays
  • βœ… Strings
  • βœ… Linked Lists

It works best when the data is sorted or can be processed from left to right or both ends.

1. Opposite Ends (Converging Pointers)

left                            right
 ↓                                ↓
 --- --- --- --- --- --- --- --- ---
| 2 | 1 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
 --- --- --- --- --- --- --- --- ---
        β†’ β†’ β†’ β†’   ← ← ← ←
  (pointers move toward each other)

When to Use:

  • When the array is sorted, and you want to find pairs that meet a condition (e.g., sum equals target).
  • When you need to reverse an array or string (sorting is NOT required).
  • Reverse an array or string.
  • Check for a palindrome.
  • Find a pair of numbers in a sorted array that sums to a target.

Example Problem:

Find if there are two numbers in a sorted array that add up to a target.

πŸ”΄ Brute Force (Slow Way):

function hasPairWithSum(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === target) {
        return true;
      }
    }
  }
  return false;
}

βœ… Two Pointer (Fast Way):

function hasPairWithSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) {
      return true;
    }
    else if (sum < target) {
      left++;
    }
    else {
      right--;
    }
  }
  return false;
}

πŸ”΄ Brute Force Approach (with Extra Space)

This approach creates a new array and fills it from the end of the original one.

function reverseArrayBruteForce(arr) {
  const reversed = [];
  for (let i = arr.length - 1; i >= 0; i--) {
    reversed.push(arr[i]);
  }
  return reversed;
}
 
// Example
console.log(reverseArrayBruteForce([1, 2, 3, 4])); // [4, 3, 2, 1]

βœ… Two Pointer Approach (In-Place)

This method swaps elements from both ends of the array, using no extra space.

function reverseArrayTwoPointer(arr) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    // Swap values
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}
 
// Example
console.log(reverseArrayTwoPointer([1, 2, 3, 4])); // [4, 3, 2, 1]

2. Same Direction (Forward Pointers)

slow      fast
 ↓         ↓
 --- --- --- --- --- --- --- --- ---
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
 --- --- --- --- --- --- --- --- ---
   β†’     β†’     β†’     β†’
(slow moves 1 step, fast moves 2 steps)

When to Use:

  • When you want to compare or track positions moving in the same direction.
  • When solving problems with fast and slow pointers (like finding the middle of a linked list or detecting a loop).
  • When you need to remove duplicates or compress data in-place in an array or string.
  • When you're scanning a single array, string, or linked list from start to end using two pointers.

Example Problem:

Find the middle of a linked list.

πŸ”΄ Brute Force (Slow Way):

function findMiddle(head) {
  let count = 0, node = head;
  while (node) {
    count++;
    node = node.next;
  }
  node = head;
  for (let i = 0; i < Math.floor(count / 2); i++) {
    node = node.next;
  }
  return node;
}

βœ… Two Pointer (Fast Way):

function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

3. Sliding Window

start     end
 ↓         ↓
 --- --- --- --- --- --- --- --- ---
| 2 | 3 | 1 | 2 | 4 | 3 |   |   |   |
 --- --- --- --- --- --- --- --- ---
      β†’       β†’
(window moves by adjusting start/end)

When to Use:

  • When working with subarrays or substrings.
  • When you want to find maximum/minimum sum, length, or count within a range.
  • When the window size is fixed or can change dynamically.

Example Problem:

Find the maximum sum of subarray of size k.

πŸ”΄ Brute Force (Slow Way):

function maxSum(arr, k) {
  let max = -Infinity;
  for (let i = 0; i <= arr.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) {
      sum += arr[j];
    }
    max = Math.max(max, sum);
  }
  return max;
}

βœ… Sliding Window (Fast Way):

function maxSum(arr, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];
  let max = sum;
  for (let i = k; i < arr.length; i++) {
    sum = sum + arr[i] - arr[i - k];
    max = Math.max(max, sum);
  }
  return max;
}

4. Parallel Pointers

Array 1:     i
             ↓
         β”Œβ”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”
         | 1 | 3 | 5 | 7 | 9 |
         β””β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”˜

Array 2:         j
                 ↓
         β”Œβ”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”¬β”€β”€β”€β”
         | 2 | 3 | 6 | 8 | 9 |
         β””β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”΄β”€β”€β”€β”˜

πŸ”„ Both pointers move forward to compare values:
- If values match ➝ do something (like store or print).
- If not, move the pointer with the smaller value.

When to Use:

  • You are working with two arrays, usually sorted.
  • You want to merge two arrays into one.
  • You need to compare values from both arrays.
  • You want to find common elements between arrays.
  • You are checking for duplicates across two lists.
  • You are solving problems where two lists are scanned together.

Example Problem:

Merge two sorted arrays into one sorted array.

πŸ”΄ Brute Force (Slow Way):

function mergeArrays(arr1, arr2) {
  return [...arr1, ...arr2].sort((a, b) => a - b);
}

βœ… Two Pointer (Fast Way):

function mergeArrays(arr1, arr2) {
  let i = 0, j = 0, result = [];
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) result.push(arr1[i++]);
    else result.push(arr2[j++]);
  }
  while (i < arr1.length) result.push(arr1[i++]);
  while (j < arr2.length) result.push(arr2[j++]);
  return result;
}

Summary

TypeUse Case
Opposite EndsSorted arrays, pairs, reverse
Same DirectionLinked lists, find middle
Sliding WindowSubarrays, substrings, max sum
Parallel PointersMerging two sorted arrays

βœ… Use two pointers to make your code faster and cleaner!

Related Question

Does Two Pointer Work Only on Sorted Arrays?

No, the two-pointer technique does not only work on sorted arrays. But whether the array needs to be sorted depends on the problem you're solving.

When Sorting is Required ?

Two pointers need a sorted array when:

  • You're trying to find a pair with a target sum.
  • You're using opposite-end (converging) pointers.
  • You're solving problems where the order of elements is important for the logic to work.
// Find if a pair sums to target
function hasPairWithSum(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return true;
    if (sum < target) left++;
    else right--;
  }
  return false;
}
// This only works if `arr` is sorted!

When Sorting is NOT Required ?

Two pointers can be used on unsorted data in cases like:

  • Fast and slow pointer in a linked list (e.g., to find the middle or detect cycles).
  • Sliding window on arrays or strings (e.g., finding the longest substring with no repeats).
  • Parallel pointers while traversing two different arrays or lists.
// Find middle of linked list
function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}
// Works on linked list, no sorting needed!

Example

Reverse Vowels of a String

// Example: "IceCreAm" ➝ "AceCreIm"
// Input: s = "IceCreAm"
// Output: "AceCreIm"
 
const reverseVowels = (s) => {
  if (typeof s !== 'string' || s.length <= 1) {
    return s;
  }
 
  const str = s.split('');
  let left = 0;
  let right = str.length - 1;
 
  while (left < right) {
    if (!isVowel(str[left])) {
      left++;
    } else if (!isVowel(str[right])) {
      right--;
    } else {
      [str[left], str[right]] = [str[right], str[left]];
      left++;
      right--;
    }
  }
  return str.join('');
};
 
function isVowel(char) {
  if (typeof char !== 'string' || char.length !== 1) {
    return false;
  }
  const vowels = 'aeiouAEIOU';
  return vowels.includes(char);
}
 
// Test
const s = 'IceCreAm';
console.log(reverseVowels(s)); // Output: "AceCreIm"