Problems

Master two pointers by solving these carefully selected problems. Review the Code Templates for reusable implementations.

Easy

1. Valid Palindrome

Brief: Check if a string reads the same forwards and backwards, ignoring non-alphanumeric characters.
Why this pattern?: Compare characters from both ends, moving inward.
Key Insight: Skip non-alphanumeric characters while comparing.

  flowchart LR
    A["'A'"] --- B["left"]
    C["'a'"] --- D["right"]
    B --> E["Compare: A == a"]
    D --> E

function isPalindrome(s) {
    let left = 0, right = s.length - 1;

    while (left < right) {
        while (left < right && !isAlphaNum(s[left])) left++;
        while (left < right && !isAlphaNum(s[right])) right--;

        if (s[left].toLowerCase() !== s[right].toLowerCase()) {
            return false;
        }
        left++; right--;
    }
    return true;
}

function isAlphaNum(c) {
    return /[a-zA-Z0-9]/.test(c);
}

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum(): left += 1
        while left < right and not s[right].isalnum(): right -= 1

        if s[left].lower() != s[right].lower():
            return False
        left += 1; right -= 1
    return True

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;

    while (left < right) {
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

        if (Character.toLowerCase(s.charAt(left)) !=
            Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++; right--;
    }
    return true;
}

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;

    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;

        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++; right--;
    }
    return true;
}

func isPalindrome(s string) bool {
    left, right := 0, len(s)-1

    for left < right {
        for left < right && !isAlphaNum(s[left]) { left++ }
        for left < right && !isAlphaNum(s[right]) { right-- }

        if strings.ToLower(string(s[left])) != strings.ToLower(string(s[right])) {
            return false
        }
        left++; right--
    }
    return true
}

func isAlphaNum(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9')
}

def is_palindrome(s)
  left, right = 0, s.length - 1

  while left < right
    left += 1 while left < right && !s[left].match?(/[a-zA-Z0-9]/)
    right -= 1 while left < right && !s[right].match?(/[a-zA-Z0-9]/)

    return false if s[left].downcase != s[right].downcase
    left += 1; right -= 1
  end
  true
end

Complexity: Time

O(N)

| Space

O(1)

2. Remove Duplicates from Sorted Array

Brief: Remove duplicates in-place from sorted array, return new length.
Why this pattern?: Slow pointer tracks unique elements, fast pointer scans.
Key Insight: Only copy when fast finds a new unique value.

function removeDuplicates(nums) {
    if (nums.length === 0) return 0;
    let slow = 0;

    for (let fast = 1; fast < nums.length; fast++) {
        if (nums[fast] !== nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

def removeDuplicates(nums: list) -> int:
    if not nums:
        return 0
    slow = 0

    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int slow = 0;

    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;

    for (int fast = 1; fast < nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

func removeDuplicates(nums []int) int {
    if len(nums) == 0 { return 0 }
    slow := 0

    for fast := 1; fast < len(nums); fast++ {
        if nums[fast] != nums[slow] {
            slow++
            nums[slow] = nums[fast]
        }
    }
    return slow + 1
}

def remove_duplicates(nums)
  return 0 if nums.empty?
  slow = 0

  (1...nums.length).each do |fast|
    if nums[fast] != nums[slow]
      slow += 1
      nums[slow] = nums[fast]
    end
  end
  slow + 1
end

Complexity: Time

O(N)

| Space

O(1)

Medium

3. Two Sum II - Input Array Is Sorted

Brief: Find two numbers in sorted array that sum to target.
Why this pattern?: Sorted array allows binary search via two pointers.
Key Insight: Move left if sum too small, right if too large.

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

    while (left < right) {
        const sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1]; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return [-1, -1];
}

def twoSum(numbers: list, target: int) -> list:
    left, right = 0, len(numbers) - 1

    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]  # 1-indexed
        elif total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return new int[]{left + 1, right + 1}; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;

    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            return {left + 1, right + 1}; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {-1, -1};
}

func twoSum(numbers []int, target int) []int {
    left, right := 0, len(numbers)-1

    for left < right {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left + 1, right + 1} // 1-indexed
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{-1, -1}
}

def two_sum(numbers, target)
  left, right = 0, numbers.length - 1

  while left < right
    sum = numbers[left] + numbers[right]
    if sum == target
      return [left + 1, right + 1] # 1-indexed
    elsif sum < target
      left += 1
    else
      right -= 1
    end
  end
  [-1, -1]
end

Complexity: Time

O(N)

| Space

O(1)

4. Container With Most Water

Brief: Find two lines that together with x-axis form container holding most water.
Why this pattern?: Start wide, narrow by moving the shorter line inward.
Key Insight: Moving the shorter line might find a taller one; moving the taller cannot help.

  flowchart TD
    A["Start: left=0, right=n-1"] --> B["Calculate area = min(h[l],h[r]) * (r-l)"]
    B --> C{"h[left] < h[right]?"}
    C -->|Yes| D["left++"]
    C -->|No| E["right--"]
    D --> F{"left < right?"}
    E --> F
    F -->|Yes| B
    F -->|No| G["Return max area"]

function maxArea(height) {
    let left = 0, right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

def maxArea(height: list) -> int:
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        area = min(height[left], height[right]) * (right - left)
        max_area = max(max_area, area)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_area

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxArea = 0;

    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        maxArea = max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

func maxArea(height []int) int {
    left, right := 0, len(height)-1
    maxArea := 0

    for left < right {
        h := min(height[left], height[right])
        area := h * (right - left)
        if area > maxArea { maxArea = area }

        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

func min(a, b int) int {
    if a < b { return a }
    return b
}

def max_area(height)
  left, right = 0, height.length - 1
  max_area = 0

  while left < right
    area = [height[left], height[right]].min * (right - left)
    max_area = [max_area, area].max

    if height[left] < height[right]
      left += 1
    else
      right -= 1
    end
  end
  max_area
end

Complexity: Time

O(N)

| Space

O(1)

5. 3Sum

Brief: Find all unique triplets that sum to zero.
Why this pattern?: Fix one element, use two pointers for remaining pair.
Key Insight: Sort first, skip duplicates to avoid repeated triplets.

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;

        let left = i + 1, 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;
}

def threeSum(nums: list) -> list:
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]: left += 1
                while left < right and nums[right] == nums[right - 1]: right -= 1
                left += 1; right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(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;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;

    for (int i = 0; i < (int)nums.size() - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({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;
}

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    result := [][]int{}

    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }

        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i] + nums[left] + nums[right]
            if sum == 0 {
                result = append(result, []int{nums[i], nums[left], nums[right]})
                for left < right && nums[left] == nums[left+1] { left++ }
                for left < right && nums[right] == nums[right-1] { right-- }
                left++; right--
            } else if sum < 0 {
                left++
            } else {
                right--
            }
        }
    }
    return result
}

def three_sum(nums)
  nums.sort!
  result = []

  (0...nums.length - 2).each do |i|
    next if i > 0 && nums[i] == nums[i - 1]

    left, right = i + 1, nums.length - 1
    while left < right
      sum = nums[i] + nums[left] + nums[right]
      if sum == 0
        result << [nums[i], nums[left], nums[right]]
        left += 1 while left < right && nums[left] == nums[left + 1]
        right -= 1 while left < right && nums[right] == nums[right - 1]
        left += 1; right -= 1
      elsif sum < 0
        left += 1
      else
        right -= 1
      end
    end
  end
  result
end

Complexity: Time

O(N^2)

| Space

O(1)

6. Sort Colors

Brief: Sort array of 0s, 1s, and 2s in-place (Dutch National Flag).
Why this pattern?: Three pointers partition array into three regions.
Key Insight: low tracks 0s boundary, high tracks 2s boundary, mid scans.

function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++; mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

def sortColors(nums: list) -> None:
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

public void sortColors(int[] nums) {
    int low = 0, mid = 0, high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low]; nums[low] = nums[mid]; nums[mid] = temp;
            low++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            int temp = nums[mid]; nums[mid] = nums[high]; nums[high] = temp;
            high--;
        }
    }
}

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;

    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++; mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

func sortColors(nums []int) {
    low, mid, high := 0, 0, len(nums)-1

    for mid <= high {
        if nums[mid] == 0 {
            nums[low], nums[mid] = nums[mid], nums[low]
            low++; mid++
        } else if nums[mid] == 1 {
            mid++
        } else {
            nums[mid], nums[high] = nums[high], nums[mid]
            high--
        }
    }
}

def sort_colors(nums)
  low, mid, high = 0, 0, nums.length - 1

  while mid <= high
    if nums[mid] == 0
      nums[low], nums[mid] = nums[mid], nums[low]
      low += 1; mid += 1
    elsif nums[mid] == 1
      mid += 1
    else
      nums[mid], nums[high] = nums[high], nums[mid]
      high -= 1
    end
  end
end

Complexity: Time

O(N)

| Space

O(1)

Hard

7. Trapping Rain Water

Brief: Calculate water trapped after rain given elevation map.
Why this pattern?: Track max heights from both sides, process shorter side.
Key Insight: Water at position depends on min of left-max and right-max.

function trap(height) {
    let left = 0, right = height.length - 1;
    let leftMax = 0, rightMax = 0, 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;
}

def trap(height: list) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max, water = 0, 0, 0

    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

public int trap(int[] height) {
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, 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;
}

int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0, 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;
}

func trap(height []int) int {
    left, right := 0, len(height)-1
    leftMax, rightMax, water := 0, 0, 0

    for 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
}

def trap(height)
  left, right = 0, height.length - 1
  left_max, right_max, water = 0, 0, 0

  while left < right
    if height[left] < height[right]
      if height[left] >= left_max
        left_max = height[left]
      else
        water += left_max - height[left]
      end
      left += 1
    else
      if height[right] >= right_max
        right_max = height[right]
      else
        water += right_max - height[right]
      end
      right -= 1
    end
  end
  water
end

Complexity: Time

O(N)

| Space

O(1)

Recommended Study Order

Valid Palindrome: Learn basic opposite direction pattern
Remove Duplicates: Master same direction pattern
Two Sum II: Apply to sum problems
Container With Most Water: Understand greedy pointer movement
3Sum: Combine fixed element with two pointers
Sort Colors: Three-pointer variation
Trapping Rain Water: Advanced application with state tracking

Study Tip: For each problem, first identify which two-pointer variation applies, then adapt the template accordingly.