Pattern 3: Two Pointers

• Overview
  • When to Use the Two Pointers Pattern
  • Key Concepts of Two Pointers
  • Common Two Pointers Problem Categories
  • Advantages of Two Pointers
  • Common Challenges and Tips
• Visualization
• Example of visualization
• List of problems that I have solved
  • Easy
  • Medium
  • Hard

Overview

The Two Pointers pattern is a common algorithmic technique used to solve a variety of problems efficiently, especially those involving arrays or strings. By strategically placing and moving two pointers (or indices) within the input, you can reduce the need for nested loops, often improving time complexity from O(n^2) to O(n) or O(nlogn).

When to Use the Two Pointers Pattern

1. Sorted Arrays:

   • When the input array is sorted, two pointers can help efficiently find elements meeting a specific condition (e.g., sums, differences, or target values).

2. Searching for Pairs/Triplets:

   • Finding pairs or triplets that satisfy a specific sum or condition.

3. Partitioning Problems:

   • Rearranging arrays based on conditions (e.g., separating 0s and 1s, or Dutch National Flag problems).

4. Optimization Problems:

   • Maximizing or minimizing a result, such as the largest container that holds water.

5. Palindrome Problems:

   • Verifying or constructing palindromic strings.

Key Concepts of Two Pointers

1. Two Pointers Moving Towards Each Other:

   • One pointer starts at the beginning, and the other starts at the end.
   • Common in problems like:
     • Validating palindromes.
     • Container with most water.
     • Two Sum (sorted input).

2. Two Pointers Moving in the Same Direction:

   • Both pointers move from left to right but at different speeds or under specific conditions.
   • Common in problems like:
     • Removing duplicates from a sorted array.
     • Finding the minimal size subarray sum.

3. Fixed Pointer + Moving Pointer:

   • One pointer is fixed, and the other explores the array.
   • Common in triplet problems like 3Sum or partitioning problems like Sort Colors.

Common Two Pointers Problem Categories

1. Two-Pointer Search:

   • Problems like finding two numbers that sum to a target in a sorted array.

2. Partitioning and Rearrangement:

   • Problems like sorting 0s, 1s, and 2s in a single pass.

3. Palindrome Checking and String Manipulation:

   • Problems like verifying if a string is a palindrome.

4. Maximizing/Minimizing Results:

   • Problems like trapping rainwater or maximizing the area in the "Container with Most Water" problem.

Advantages of Two Pointers

• Efficient:

  • Often reduces time complexity significantly.
  • Typically operates in (O(n)) or (O(n \log n)) when combined with sorting.

• Intuitive:

  • Provides a straightforward, logical structure for problems involving pairs, triplets, or ranges.

• Space Efficient:

  • Works in-place, often requiring (O(1)) additional space.

Common Challenges and Tips

1. Sorted Inputs:

   • If the input isn't sorted but sorting helps, consider preprocessing with (O(nlogn) sorting.

2. Edge Cases:

   • Handle cases with empty inputs, single elements, or overlapping ranges.

3. Understanding Conditions:

   • Clearly define when and how to move the pointers based on the problem constraints.

Visualization

• Above theory is fine and is easier to read but diffcult to implement.
• If you want to get better at this pattern, you need to visualize how the two points are moving and behaving (Which is easier said than done).
• Use following helper methods to visualize the array along with the two pointers as you are iterating over it.
• Call the helper methods from inside the for loop. Use the prefix arguments segregate two different lines in the algorithm

• Left pointer is reprented as (), right pointer is represented as []. If both pointers point at same index, it is represented as [()].

• int[] : Integer Array
  

private void tpi(int[] s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length; i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s[i]);
        } else if (i == l) {
            System.out.printf("(%s)", s[i]);
        } else if (i == r) {
            System.out.printf("[%s]", s[i]);
        } else {
            System.out.print(s[i]);
        }
        System.out.print(" ");
    }
    System.out.println();
}

• char[] : Character Array

// Two pointer char array
private void tpc(char[] s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length; i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s[i]);
        } else if (i == l) {
            System.out.printf("(%s)", s[i]);
        } else if (i == r) {
            System.out.printf("[%s]", s[i]);
        } else {
            System.out.print(s[i]);
        }
        System.out.print(" ");
    }
    System.out.println();
}

• String : String

// Two pointer string
private void tps(String s, int l, int r, String... prefix) {
    if (prefix.length == 0) {
        prefix = new String[] { "" };
    }
    System.out.print(prefix[0]);
    for (int i = 0; i < s.length(); i++) {
        if (i == l && i == r) {
            System.out.printf("[(%s)]", s.charAt(i));
        } else if (i == l) {
            System.out.printf("(%s)", s.charAt(i));
        } else if (i == r) {
            System.out.printf("[%s]", s.charAt(i));
        } else {
            System.out.print(s.charAt(i));
        }
        System.out.print(" ");
    }
    System.out.println();
}

Example of visualization

For example for leetcode problem : 283. Move zeroes
Solution

class Solution {

    private void tpi(int[] s, int l, int r, String... prefix) {
        if (prefix.length == 0) {
            prefix = new String[] { "" };
        }
        System.out.print(prefix[0]);
        for (int i = 0; i < s.length; i++) {
            if (i == l && i == r) {
                System.out.printf("[(%s)]", s[i]);
            } else if (i == l) {
                System.out.printf("(%s)", s[i]);
            } else if (i == r) {
                System.out.printf("[%s]", s[i]);
            } else {
                System.out.print(s[i]);
            }
            System.out.print(" ");
        }
        System.out.println();
    }

    public void moveZeroes(int[] nums) {
        int l = 0, r = 0;
        while (r < nums.length) {
            tpi(nums, l, r);
            if (nums[r] != 0) {
                nums[l] = nums[r];
                l++;
                tpi(nums, l, r, "Replaced: ");
            }
            r++;
        }
        while (l < nums.length) {
            nums[l++] = 0;
            tpi(nums, l, r, "Remaining: ");
        }
    }

}

Input: nums = [0,1,0,3,12]

Std out

[(0)] 1 0 3 12 
(0) [1] 0 3 12 
Replaced: 1 [(1)] 0 3 12 
1 (1) [0] 3 12 
1 (1) 0 [3] 12 
Replaced: 1 3 (0) [3] 12 
1 3 (0) 3 [12] 
Replaced: 1 3 12 (3) [12] 
Remaining: 1 3 12 0 (12) 
Remaining: 1 3 12 0 0 

List of problems that I have solved

Easy

Medium

Hard