Skip to main content

Multiple Pointers Pattern

The Multiple Pointers pattern involves creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on a certain condition.

What is Multiple Pointers?​

This pattern creates pointers or values that correspond to array indices and move through the data structure in tandem or in opposite directions to find a pair of elements that match certain conditions.

When to Use?​

  • Working with sorted arrays
  • Finding pairs in an array that sum to a target
  • Finding unique values
  • Partitioning arrays
  • Detecting cycles in linked lists

Common Applications​

  • Two sum problems
  • Three sum problems
  • Finding unique values
  • Removing duplicates
  • Palindrome verification

Time Complexity​

Most multiple pointers solutions achieve O(n) time complexity, compared to O(n²) with nested loops.

Example Problems​

1. Sum Zero​

Problem Description​

Write a function that finds the first pair of numbers in a sorted array that sum to zero.

Example​

Input: [-3, -2, -1, 0, 1, 2, 3];
Output: [-3, 3];

Input: [-2, 0, 1, 3];
Output: undefined;

Solution​

function sumZero(arr) {
	let left = 0;
	let right = arr.length - 1;

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

		if (sum === 0) {
			return [arr[left], arr[right]];
		} else if (sum > 0) {
			right--;
		} else {
			left++;
		}
	}
}

Time Complexity​

  • Time: O(n)
  • Space: O(1)

2. Count Unique Values​

Problem Description​

Implement a function that counts unique values in a sorted array.

Example​

Input: [1, 1, 1, 2, 3, 3, 4, 4, 5, 6];
Output: 6;

Input: [-2, -1, -1, 0, 1];
Output: 4;

Solution​

function countUniqueValues(arr) {
	if (arr.length === 0) return 0;

	let i = 0;

	for (let j = 1; j < arr.length; j++) {
		if (arr[i] !== arr[j]) {
			i++;
			arr[i] = arr[j];
		}
	}

	return i + 1;
}

Time Complexity​

  • Time: O(n)
  • Space: O(1)

Practice Problems​

To master the multiple pointers pattern, try solving these problems:

  1. Three Sum
  2. Remove Duplicates from Sorted Array
  3. Find Pair with Target Sum
  4. Dutch National Flag Problem
  5. Move Zeros to End

Common Multiple Pointers Strategies​

  1. Two Pointers from Ends

    • Start pointers at beginning and end
    • Move inward based on conditions

  2. Fast and Slow Pointers

    • One pointer moves faster than other
    • Used for cycle detection

  3. Multiple Pointers in Same Direction

    • Multiple pointers moving forward
    • Used for window-like operations

Tips for Solving Multiple Pointers Problems​

  1. Consider if array needs to be sorted
  2. Choose appropriate pointer movement strategy
  3. Handle edge cases (empty arrays, single element)
  4. Consider pointer initialization positions
  5. Think about termination conditions

Common Pitfalls​

  1. Not Checking Array Boundaries

    • Always ensure pointers stay within bounds

  2. Incorrect Pointer Movement

    • Make sure pointers move in correct direction
    • Handle equal values correctly

  3. Forgetting Edge Cases

    • Empty arrays
    • Single element arrays
    • Duplicate elements

Additional Resources​

Last updated on