03. Two Pointers and Sliding Window

📋 Jump to Takeaways

Two pointers and sliding window are techniques that turn O(n²) brute-force solutions into O(n). They work by maintaining a window or pair of indices that move through the array in a controlled way, avoiding redundant work.

Two Pointers: Opposite Direction

Two pointers start at opposite ends and move toward each other. Used when the array is sorted or when you need to compare elements from both ends.

LeetCode 167 - Two Sum II - Input Array Is Sorted

// Two Sum on a sorted array — O(n)
func twoSumSorted(nums []int, target int) []int {
    l, r := 0, len(nums)-1
    for l < r {
        sum := nums[l] + nums[r]
        if sum == target {
            return []int{l, r}
        } else if sum < target {
            l++ // need larger sum
        } else {
            r-- // need smaller sum
        }
    }
    return nil
}

Why it works: if the sum is too small, moving l right increases it. If too large, moving r left decreases it. Each element is visited at most once → O(n).

Other opposite-direction problems:

Container with most water — maximize area between two lines
Valid palindrome — compare from both ends
3Sum — fix one element, two-pointer on the rest

Two Pointers: Same Direction

Both pointers move left to right, but at different speeds. The "fast" pointer scans every element; the "slow" pointer tracks a position of interest.

LeetCode 26 - Remove Duplicates from Sorted Array

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

The slow pointer marks where the next valid element should go. The fast pointer finds valid elements. This is the "read/write pointer" pattern.

Two Pointers: Fast and Slow (Floyd's)

Used on linked lists to detect cycles and find midpoints:

LeetCode 141 - Linked List Cycle

// Detect cycle in linked list
func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

Sliding Window: Fixed Size

Maintain a window of exactly K elements. Slide it across the array — add the new right element, remove the old left element.

// Maximum sum of K consecutive elements — O(n)
func maxSumK(nums []int, k int) int {
    windowSum := 0
    for i := 0; i < k; i++ {
        windowSum += nums[i]
    }
    maxSum := windowSum
    for i := k; i < len(nums); i++ {
        windowSum += nums[i] - nums[i-k] // add right, remove left
        if windowSum > maxSum {
            maxSum = windowSum
        }
    }
    return maxSum
}

Without sliding window: check every subarray of size K → O(n×k). With sliding window: O(n).

Sliding Window: Variable Size

The window expands right until a condition is violated, then shrinks from the left until the condition is restored. This is the more powerful (and common) pattern.

Template:

func slidingWindow(s string) int {
    left := 0
    best := 0
    // state tracking (map, counter, etc.)

    for right := 0; right < len(s); right++ {
        // expand: add s[right] to window state

        for /* window is invalid */ {
            // shrink: remove s[left] from window state
            left++
        }

        // update best answer with current valid window
        best = max(best, right-left+1)
    }
    return best
}

LeetCode 3 - Longest Substring Without Repeating Characters

func lengthOfLongestSubstring(s string) int {
    seen := map[byte]int{} // char → last index
    left := 0
    best := 0
    for right := 0; right < len(s); right++ {
        if idx, ok := seen[s[right]]; ok && idx >= left {
            left = idx + 1 // shrink past the duplicate
        }
        seen[s[right]] = right
        if right-left+1 > best {
            best = right - left + 1
        }
    }
    return best
}

LeetCode 209 - Minimum Size Subarray Sum

func minSubArrayLen(target int, nums []int) int {
    left, sum := 0, 0
    best := len(nums) + 1
    for right := 0; right < len(nums); right++ {
        sum += nums[right] // expand
        for sum >= target {
            if right-left+1 < best {
                best = right - left + 1
            }
            sum -= nums[left] // shrink
            left++
        }
    }
    if best > len(nums) {
        return 0
    }
    return best
}

Kadane's Algorithm

Kadane's solves the maximum subarray sum problem in O(n). At each position, decide: extend the current subarray, or start fresh here.

LeetCode 53 - Maximum Subarray

func maxSubArray(nums []int) int {
    maxSum := nums[0]
    curSum := nums[0]
    for i := 1; i < len(nums); i++ {
        if curSum+nums[i] > nums[i] {
            curSum += nums[i] // extend
        } else {
            curSum = nums[i] // restart
        }
        if curSum > maxSum {
            maxSum = curSum
        }
    }
    return maxSum
}

The logic: if curSum has gone negative, it can only hurt future elements — drop it and restart. This is the same "extend or reset" idea as variable-size sliding window, but without an explicit left pointer.

Why it belongs here: Kadane's is not DP in the traditional sense (no table, no subproblem lookup). It's a single-pass greedy scan that maintains running state — the same mental model as sliding window.

LeetCode 152 - Maximum Product Subarray

Find the contiguous subarray with the largest product. Negatives can flip signs — a very negative minProd times a negative number becomes the new max. Track both maxProd and minProd at each step.

func maxProduct(nums []int) int {
    maxProd, minProd, result := nums[0], nums[0], nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxProd, minProd = minProd, maxProd
        }
        if nums[i] > maxProd*nums[i] {
            maxProd = nums[i]
        } else {
            maxProd = maxProd * nums[i]
        }
        if nums[i] < minProd*nums[i] {
            minProd = nums[i]
        } else {
            minProd = minProd * nums[i]
        }
        if maxProd > result {
            result = maxProd
        }
    }
    return result
}

When to Use Two Pointers vs Sliding Window

Technique	When
Opposite-direction pointers	Sorted array, pair problems, palindromes
Same-direction (read/write)	In-place removal, compaction
Fast/slow pointers	Linked list cycles, finding midpoints
Fixed sliding window	Subarray/substring of exact size K
Variable sliding window	Longest/shortest subarray satisfying a condition
Kadane's algorithm	Maximum/minimum subarray sum or product

The Key Insight

Both techniques avoid recomputation. Instead of recalculating from scratch for every position (O(n²)), they maintain running state and update it incrementally as pointers move (O(n)).

Practice Problems

Problem	Difficulty	Link
Valid Palindrome	Easy	LeetCode 125
Remove Duplicates from Sorted Array	Easy	LeetCode 26
Move Zeroes	Easy	LeetCode 283
Two Sum II (sorted)	Medium	LeetCode 167
3Sum	Medium	LeetCode 15
Container With Most Water	Medium	LeetCode 11
Longest Substring Without Repeating Characters	Medium	LeetCode 3
Minimum Size Subarray Sum	Medium	LeetCode 209
Minimum Window Substring	Hard	LeetCode 76
Maximum Subarray	Medium	LeetCode 53
Maximum Product Subarray	Medium	LeetCode 152
Trapping Rain Water	Hard	LeetCode 42

Key Takeaways

Two pointers and sliding window turn O(n²) into O(n) by avoiding redundant work
Opposite-direction: sorted arrays, pair sums, palindromes
Same-direction: in-place compaction, read/write pointer
Fixed window: add right, remove left, constant size
Variable window: expand right until invalid, shrink left until valid
The variable sliding window template solves dozens of "longest/shortest subarray" problems
Both techniques maintain running state instead of recomputing from scratch
Kadane's algorithm: extend the subarray if it helps, restart if running sum is negative — O(n)