Kata: Two-Pointer Technique

Table of contents

Problem Statement

Solve three problems using the two-pointer technique:

Problem 1: Pair Sum

Given a sorted array and a target sum, find two numbers that add up to the target. Return their indices.

Problem 2: Palindrome Check

Check if a string is a palindrome, ignoring non-alphanumeric characters and case.

Problem 3: Container With Most Water

Given an array of heights, find two lines that together with the x-axis form a container holding the most water. Return the maximum area.

Concepts

The two-pointer technique uses two indices that move toward each other (or in the same direction) to solve problems in O(n) that would otherwise require O(n^2).

Patterns:

• Opposite ends: Start at both ends, move inward (pair sum, container)
• Same direction: Fast/slow pointers (linked list cycle detection, removing duplicates)

Boilerplate

TypeScript

// two-pointer.ts
function pairSum(nums: number[], target: number): [number, number] | null {
  // TODO
  return null;
}

function isPalindrome(s: string): boolean {
  // TODO
  return false;
}

function maxArea(heights: number[]): number {
  // TODO
  return 0;
}

Hints

Solution

TypeScript

function pairSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

  while (left < right) {
    const sum = nums[left] + nums[right];

    if (sum === target) return [left, right];
    if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return null;
}

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

  while (left < right) {
    // Skip non-alphanumeric
    while (left < right && !/[a-zA-Z0-9]/.test(s[left])) left++;
    while (left < right && !/[a-zA-Z0-9]/.test(s[right])) right--;

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

    left++;
    right--;
  }

  return true;
}

function maxArea(heights: number[]): number {
  let left = 0;
  let right = heights.length - 1;
  let max = 0;

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

    if (heights[left] < heights[right]) {
      left++;
    } else {
      right--;
    }
  }

  return max;
}

Python

def pair_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return (left, right)
        elif total < target:
            left += 1
        else:
            right -= 1

    return None

def is_palindrome(s: str) -> bool:
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

    # Or with two pointers:
    # 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

def max_area(heights: list[int]) -> int:
    left, right = 0, len(heights) - 1
    result = 0

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

        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1

    return result

PHP

function pairSum(array $nums, int $target): ?array {
    $left = 0;
    $right = count($nums) - 1;

    while ($left < $right) {
        $sum = $nums[$left] + $nums[$right];

        if ($sum === $target) return [$left, $right];
        if ($sum < $target) {
            $left++;
        } else {
            $right--;
        }
    }

    return null;
}

function isPalindrome(string $s): bool {
    $cleaned = preg_replace('/[^a-zA-Z0-9]/', '', strtolower($s));
    return $cleaned === strrev($cleaned);
}

function maxArea(array $heights): int {
    $left = 0;
    $right = count($heights) - 1;
    $max = 0;

    while ($left < $right) {
        $area = min($heights[$left], $heights[$right]) * ($right - $left);
        $max = max($max, $area);

        if ($heights[$left] < $heights[$right]) {
            $left++;
        } else {
            $right--;
        }
    }

    return $max;
}

Complexity Analysis

The two-pointer technique consistently eliminates an order of magnitude in time complexity.

Cross-Language Notes

Python: The palindrome check with slicing (cleaned == cleaned[::-1]) is the most Pythonic solution — readable and fast thanks to optimized C internals. Python’s str.isalnum() and list comprehensions make this particularly clean.

PHP: strrev() and preg_replace provide a concise palindrome solution. PHP’s string functions are well-suited for this type of problem.

Variations: The two-pointer technique extends to:

• Three Sum: Fix one pointer, use two pointers on the rest (O(n^2))
• Sliding Window: Same-direction pointers for substring/subarray problems
• Fast/Slow: Floyd’s cycle detection in linked lists