Two Pointers: Intermediate

Where two-pointer problems get real: 3Sum, partitioning, and multi-pointer coordination

Where two-pointer problems get real: 3Sum, partitioning, and multi-pointer coordination

Category

Python

Difficulty

intermediate

Duration

30 minutes

Challenges

0 hands-on challenges

Topics covered: 3Sum: Fix One, Scan Two, Duplicate Skipping: The Detail That Breaks Candidates, Container With Most Water: The Squeeze Pattern, Partitioning: Dutch National Flag, K-Way Merge: Scaling Two Pointers

Lesson Sections

1. 3Sum: Fix One, Scan Two (concepts: py3Sum, pyFixAndScan)

   3Sum is the single most asked medium-difficulty two-pointer problem in technical interviews. Given an array of integers, find all unique triplets that sum to zero. The naive approach tries every triple: O(n^3). The optimized approach sorts the array, fixes one element, and uses two pointers to find the remaining pair: O(n^2). This is a reduction technique: reduce a 3-element problem to a 2-element problem you already know how to solve. Here is the mental model. Sort the array first. Then loop th

2. Duplicate Skipping: The Detail That Breaks Candidates (concepts: pyDuplicateSkipping, pyDedup)

   Duplicate handling is where most candidates lose points on two-pointer problems. The logic is subtle: you need to skip values you have already used as the fixed element (to avoid duplicate triplets), AND skip values you have already used as the left/right pair (to avoid duplicate triplets within the same fixed element). Getting either wrong produces duplicates in the output. The key insight: you skip AFTER processing, not before. After finding a valid triplet, advance left past all copies of its

3. Container With Most Water: The Squeeze Pattern (concepts: pySqueezePattern, pyGreedyTwoPointers)

   Container With Most Water (LeetCode 11) is the other classic medium two-pointer problem. Given an array of heights, find two lines that together with the x-axis form a container that holds the most water. The width is the distance between the two lines. The height is the shorter of the two lines. Maximize area = width x min(height_left, height_right). The brute force checks every pair: O(n^2). Two pointers gives you O(n). Start with pointers at opposite ends (maximum width). At each step, move t

4. Partitioning: Dutch National Flag (concepts: pyDutchNationalFlag, pyThreeWayPartition)

   The Dutch National Flag problem (LeetCode 75: Sort Colors) uses THREE pointers to partition an array into three zones in a single pass. Given an array with values 0, 1, and 2, sort it in-place without using a sorting algorithm. The trick: maintain three pointers. A 'low' pointer tracks where the next 0 should go. A 'high' pointer tracks where the next 2 should go. A 'mid' pointer scans through the array. When mid finds a 0, swap with low and advance both. When mid finds a 2, swap with high and r

5. K-Way Merge: Scaling Two Pointers (concepts: pyKWayMerge, pyHeapMerge)

   Two-pointer merge works for two sorted inputs. What about K sorted inputs? This is the K-way merge, and it is one of the most practically important algorithms in data engineering. Merging K sorted Kafka partitions. Combining K sorted output files from a Spark stage. The external sort merge step. All of these are K-way merge. The naive approach: merge two at a time, K-1 times. Each merge is O(n), and you do K-1 of them, giving O(n*K). The optimal approach: use a min-heap with K entries, one per i