Two Pointers Technique | Array Algorithms | Array

Overview

Two Pointers is a fundamental technique for solving array problems efficiently. It uses two indices moving through the array, either from opposite ends or in the same direction, to reduce time complexity from O(n²) to O(n) and space complexity to O(1) in many cases.

The technique is particularly powerful for sorted arrays, where you can make decisions about which pointer to move based on comparisons. It's also essential for in-place operations and problems requiring simultaneous processing from both ends.

Common two-pointer patterns include:

Opposite ends (palindrome, two sum)
Same direction (remove duplicates, partition)
Fast and slow (cycle detection, middle element)

Pattern 1: Two Pointers from Opposite Ends

Start with left = 0 and right = n - 1. Move them toward each other based on conditions.

Two Sum in Sorted Array:

function twoSum(nums: number[], target: number): number[] {
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const sum = nums[left] + nums[right];
    
    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  
  return [];
}

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

Container With Most Water:

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;
  
  while (left < right) {
    const width = right - left;
    const area = Math.min(height[left], height[right]) * width;
    maxArea = Math.max(maxArea, area);
    
    // Move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxArea;
}

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

Pattern 2: Two Pointers Same Direction

Both pointers move forward, often with one as "write" and one as "read".

Remove Duplicates:

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  
  let write = 0;
  
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write]) {
      write++;
      nums[write] = nums[read];
    }
  }
  
  return write + 1;
}

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

Move Zeros to End:

function moveZeroes(nums: number[]): void {
  let write = 0;
  
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) {
      nums[write] = nums[read];
      write++;
    }
  }
  
  while (write < nums.length) {
    nums[write++] = 0;
  }
}

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

Pattern 3: Fast and Slow Pointers

One pointer moves faster than the other, useful for cycle detection and finding middle elements.

Find Middle Element:

function findMiddle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  
  return slow;
}

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

Detect Cycle:

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    
    if (slow === fast) return true;
  }
  
  return false;
}

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

Pattern 4: Partitioning

Use two pointers to partition array based on a condition.

Partition Array:

function partition(nums: number[], pivot: number): number {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    if (nums[left] <= pivot) {
      left++;
    } else if (nums[right] > pivot) {
      right--;
    } else {
      [nums[left], nums[right]] = [nums[right], nums[left]];
      left++;
      right--;
    }
  }
  
  return left;
}

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

Dutch National Flag:

function sortColors(nums: number[]): void {
  let left = 0;
  let right = nums.length - 1;
  let i = 0;
  
  while (i <= right) {
    if (nums[i] === 0) {
      [nums[i], nums[left]] = [nums[left], nums[i]];
      left++;
      i++;
    } else if (nums[i] === 2) {
      [nums[i], nums[right]] = [nums[right], nums[i]];
      right--;
    } else {
      i++;
    }
  }
}

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

Pattern 5: Three Pointers

Extend two pointers to three for three-sum problems.

Three Sum:

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const result: number[][] = [];
  
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    
    let left = i + 1;
    let right = nums.length - 1;
    
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  
  return result;
}

Time: O(n²), Space: O(1)

Pattern 6: Trapping Rain Water

Use two pointers to calculate trapped water.

function trap(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  
  return water;
}

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

When to Use Two Pointers

Use two pointers when:

Problem involves sorted array and finding pairs
Need in-place operations without extra space
Comparing elements from both ends
Partitioning array based on condition
Cycle detection or finding middle
Problem asks for O(1) space solution

Template (Opposite Ends)

function twoPointersTemplate(nums: number[]): number {
  let left = 0;
  let right = nums.length - 1;
  let result = 0;
  
  while (left < right) {
    // Process elements at left and right
    // Update result based on condition
    
    if (/* condition */) {
      left++;
    } else {
      right--;
    }
  }
  
  return result;
}

Template (Same Direction)

function twoPointersSameDirection(nums: number[]): number[] {
  let write = 0;
  
  for (let read = 0; read < nums.length; read++) {
    if (/* condition */) {
      nums[write] = nums[read];
      write++;
    }
  }
  
  return nums.slice(0, write);
}

Time and Space Complexity Summary

Opposite ends: O(n) time, O(1) space
Same direction: O(n) time, O(1) space
Fast/slow: O(n) time, O(1) space
Three pointers: O(n²) time, O(1) space

Practice Tips

Sort first - Many two-pointer problems require sorted arrays
Handle duplicates - Skip duplicates to avoid duplicate results
Move pointers wisely - Understand which pointer to move and when
Edge cases - Empty array, single element, all same elements
Off-by-one - Careful with left < right vs left <= right

Common Mistakes

Not sorting - Two sum on unsorted array needs hash map
Wrong pointer movement - Moving wrong pointer loses optimal solution
Duplicate handling - Not skipping duplicates causes duplicate results
Index errors - Off-by-one errors in boundary conditions
Not resetting - Forgetting to reset pointers in nested loops

Related Concepts

Sliding Window - Similar but maintains contiguous segment
Binary Search - Also uses two pointers but for search
Array Partitioning - Uses two pointers for partitioning

Two pointers is a fundamental technique. Master these patterns, and you'll be well-prepared for array manipulation problems.