Pattern #5

Two Pointers

Important interview questions, thinking patterns, pointer types, and rules for solving two pointer problems in Go.

Must Solve

15 core questions — solve these first.

  1. 1.Valid Palindrome
    easy
  2. 2.Two Sum II - Input Array Is Sorted
    medium
  3. 3.Remove Duplicates from Sorted Array
    easy
  4. 4.Remove Element
    easy
  5. 5.Move Zeroes
    easy
  6. 6.Squares of a Sorted Array
    easy
  7. 7.Reverse String
    easy
  8. 8.Reverse Words in a String
    medium
  9. 9.Container With Most Water
    medium
  10. 10.3Sum
    medium
  11. 11.3Sum Closest
    medium
  12. 12.Sort Colors
    medium
  13. 13.Backspace String Compare
    easy
  14. 14.Trapping Rain Water
    hard
  15. 15.Boats to Save People
    medium

Also Important

10 more questions worth practicing.

  1. 16.Merge Sorted Array
    easy
  2. 17.Intersection of Two Arrays
    easy
  3. 18.Is Subsequence
    easy
  4. 19.Valid Palindrome II
    easy
  5. 20.Partition Labels
    medium
  6. 21.Minimum Size Subarray Sum
    medium
  7. 22.4Sum
    medium
  8. 23.Dutch National Flag Problem
    medium
  9. 24.Remove Nth Node From End of List
    medium
  10. 25.Linked List Cycle
    easy

How to Think

  1. Array/string is sorted?Two Pointers
  2. Need pair with target?left + right
  3. Need compare from both ends?left → ← right
  4. Need remove/move in-place?read pointer + write pointer
  5. Need compare every pair?Sort + Two Pointers → O(n log n)
  6. Need triplets?Sort + Fix one + Two Pointers
  7. Need O(1) extra space?Try in-place Two Pointers

Go Quick Reference

Two Sum II — Sorted (Opposite Direction)

func twoSum(nums []int, target int) []int {
    lo, hi := 0, len(nums)-1
    for lo < hi {
        sum := nums[lo] + nums[hi]
        if sum == target {
            return []int{lo + 1, hi + 1}
        } else if sum < target {
            lo++
        } else {
            hi--
        }
    }
    return nil
}

👉 Time: O(n) | Space: O(1)

Move Zeroes (Same Direction — Slow + Fast)

func moveZeroes(nums []int) {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != 0 {
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow++
        }
    }
}

👉 Time: O(n) | Space: O(1)

Container With Most Water (Opposite Direction)

func maxArea(height []int) int {
    lo, hi := 0, len(height)-1
    best := 0
    for lo < hi {
        w := hi - lo
        h := min(height[lo], height[hi])
        if area := w * h; area > best {
            best = area
        }
        if height[lo] < height[hi] {
            lo++
        } else {
            hi--
        }
    }
    return best
}

👉 Time: O(n) | Space: O(1)

3Sum (Sort + Fix one + Two Pointers)

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }
        lo, hi := i+1, len(nums)-1
        for lo < hi {
            sum := nums[i] + nums[lo] + nums[hi]
            if sum == 0 {
                res = append(res, []int{nums[i], nums[lo], nums[hi]})
                for lo < hi && nums[lo] == nums[lo+1] { lo++ }
                for lo < hi && nums[hi] == nums[hi-1] { hi-- }
                lo++; hi--
            } else if sum < 0 { lo++ } else { hi-- }
        }
    }
    return res
}

👉 Time: O(n²) | Space: O(1)

Main Two Pointer Types

1. Opposite Direction

left → [........] ← right

Used for: Palindrome, Two Sum Sorted, Container With Most Water, 3Sum, Trapping Rain Water

2. Same Direction

slow →
fast ---->

Used for: Move Zeroes, Remove Duplicates, Remove Element, In-place modifications

3. Two Different Arrays

i → array1
j → array2

Used for: Merge Sorted Array, Intersection, Comparing sorted data

Interview Rules

  1. 1. Sorted? → Think Two Pointers
  2. 2. Pair target? → Left + Right
  3. 3. Palindrome? → Both ends
  4. 4. Remove duplicates? → Slow + Fast
  5. 5. Move items? → Read + Write
  6. 6. Merge sorted arrays? → Pointer on each
  7. 7. Triplets? → Sort + Fix one + Two Pointers
  8. 8. Need O(1) extra space? → Try in-place Two Pointers

Small Rules

  1. Rule 1: Sorted array is a big hint. Think Two Pointers or Binary Search.
  2. Rule 2: If both pointers move only forward → Usually O(n), not O(n²). Even with inner loop.
  3. Rule 3: Move the pointer that can improve the answer. sum < target → left++
  4. Rule 4: Two pointers often save extra memory. Modify original array → possible O(1) space.

Production Thinking

Merge sorted data → pointer A + pointer B

Remove invalid items → read pointer + write pointer

Compare from both sides → left + right

Memory matters (large arrays) → O(1) extra space

Remember This

Sorted + Pair      → Two Pointers
Palindrome         → Left + Right
Remove/Move        → Slow + Fast
Merge sorted data  → Pointer on both
3Sum               → Sort + Two Pointers
In-place           → Two Pointers

💡 Two Pointers is one of the highest ROI patterns. Master these 25 problems and you can handle most pointer-based interview questions.