Topic 2: Two Pointers

Canonical Questions #

Intuition: use this when linear traversal can be optimized by eliminating redundant comparisons by moving pointers strategically.

When input is sorted / can be preprocessed and sorted and we can exploit the monotonicity of the ordering.

When you want to solve a pairwise or bounded-interval problem efficiently without nested loops. These usually rely on some greedy decisions that we can make.

Array In-place Manipulations #

See Merge Sorted Array (88)
- idea is to fill from the back to use the extra space that exists

Remove Element (27)

Have to manage slot indexes (where to slot in values) and also need to find out swappable candidates from the right (because the right of the array shall be where all the “deletes” go to). That’s why there’s a bunch of while loops in this solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
   class Solution:
       def removeElement(self, nums: List[int], val: int) -> int:
           n = len(nums)
           p = 0 # pointer for non val elems
           slot = n - 1 # pointer for val elems to be swapped out -- slot

           # find rightmost non-val
           while slot >= 0 and nums[slot] == val:
               slot -= 1

           # now for the 2 pointer swap:
           while p <= slot:
               if nums[p] == val:
                   nums[p], nums[slot] = nums[slot], nums[p]
                   p += 1
                   # find new slot again:
                   while slot >= 0 and nums[slot] == val:
                       slot -= 1
               else:
                   p += 1 # just move fwd if non-val

           return p

Code Snippet 1: Remove Element (27) – 2 pointers

Pattern Extraction

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Core Insight: Use two pointers: one scans for elements to remove, one tracks the rightmost non-val element. When a val is found, swap it with the rightmost non-val and move the scan pointer forward. The boundary pointer contracts inward until the pointers converge.

Pattern Name: Two-Pointer In-Place Swap (or Partition by Swap)

Canonical Section: Array Manipulation > Two-Pointer In-Place / Partition Patterns

Recognition Signals:

Remove or partition elements in-place with O(1) space
Array order doesn’t matter (not sorted or stable removal required)
Need to know count of remaining valid elements
One pointer scans from left, one boundary pointer from right
Anti-Signals:
- Array is sorted and duplicates are involved → use lookback window instead
- Must preserve relative order of non-removed elements → shift (slower) or use different pattern
- Need to return indices of removed elements → track or store separately
- Two separate values to partition (not just one value to remove) → dual-pointer with multiple swaps
  Decision Point: Remove a single value in-place with no order constraint? → two-pointer swap from front and back. If sorted + duplicates, reach for lookback window (LC 26/80).
  Interviewer Comms: “I’ll use two pointers: one (p) scanning from the left to find val elements, one (slot) tracking the rightmost non-val element from the right. When I find a val at p, I swap it with the element at slot and move p forward. Meanwhile, I shrink slot inward to find the next non-val candidate. The loop continues until p and slot converge. Time is O(n), space is O(1).”

Pitfalls and Misconceptions

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Trap: Compare index p with val instead of element nums[p]. Why: Type confusion — `if p != val` compares an index (0, 1, 2…) with a value (e.g., 3). This accidentally works in some cases but is fundamentally wrong. Correction: Always compare elements: `if nums[p] == val`.
Trap: Forget to increment p after swapping. Why: After swapping a val element out, p must move forward to check the next position. Without p += 1, the loop may stall or enter an infinite loop. Correction: Add `p += 1` immediately after the swap.
Trap: Loop condition is `while p < slot` instead of `while p <= slot`. Why: When p = slot (pointers converge), if that position contains a non-val, it should be counted as valid. `p < slot` exits too early. Correction: Use `while p < slot` to include the convergence point.
Trap: After loop exits (when p > slot), forget to verify the convergence state. Why: Edge case when p = slot and nums[slot] is non-val — this element is still valid but not yet counted. Correction: After the loop, check `if p = slot and nums[p] != val: p += 1` to include the convergence point.
Trap: Return `n - count_of_vals` instead of `p`. Why: Trying to infer the count by counting the remaining vals is fragile and may be off-by-one. Correction: Return `p` directly, which tracks the boundary of valid elements.

Problem Mutations

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

What if we need to remove two different values (e.g., remove both 2 and 3)? (stress-test: generality) Use two slot pointers, one for each value, or partition into three regions (vals to remove, valid elements, unused). Complexity remains O(n).
What if the array is sorted and we need to preserve order of remaining elements? (stress-test: stability) Swap approach violates order. Use shift-based removal (O(n²)) or accumulate valid elements and overwrite. Lookback window pattern (LC 26) is better for this.
What if we need to count swaps or track indices of removed elements? (stress-test: output) Standard two-pointer swap doesn’t store this info. Maintain a separate list of removed indices or count swaps as you go.
What if nums is empty or all elements are val? (stress-test: edge cases) If all are val, the initial loop that finds rightmost non-val exits with slot = −1, and the main loop condition p <= slot is false immediately, returning p = 0. Correct.
What if nums contains only the target val in the first position and non-vals after? (stress-test: boundary) First iteration swaps nums[0] with the rightmost non-val, p increments, main loop continues. No special handling needed.

Remove Duplicates from Sorted Array (26)

The solution below shows the generalised form.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
   class Solution:
       def removeDuplicates(self, nums: List[int]) -> int:
           """
           We just need a pointer to slot, and we just need to keep finding the next unique element.

           This solution is generalised to k.

           We go through every number and compare the current number with the current idx (slot idx).

           There's 2 cases where we assign and increment the slot idx (i.e. "found unique"):
           1. when idx < k -- not enough window created yet
           2. when we do a lookback and we know that the current number differs from the allowed lookbacks (i.e. element @ idx - k)

           When we find a unique value, we write it to this slot and allow the slot to increment by 1 each time.
           """
           idx = 0
           k = 1
           for num in nums:
               # found a unique value:
               if idx < k or num > nums[idx - k]:
                   nums[idx] = num
                   idx += 1
           return idx

Code Snippet 2: (Generalised) Remove duplicates from Sorted Array: 1 pointer to comb through everything and another to keep track of where unique elements can be slotted in

Pattern Extraction

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Core Insight: For sorted arrays, a unique element is one that differs from its predecessor (or the element k positions back in the generalised form). Use a single pointer to scan and a slot pointer to place unique elements. Crucially: if idx < k (not enough window yet), we’re still building; once idx >= k, check if num > nums[idx − k].

Pattern Name: Sorted Array De-duplication via Lookback Window

Canonical Section: Array Manipulation > Two-Pointer In-Place / Sorted Array Patterns

Recognition Signals:

Array is sorted (ascending)
Remove duplicates or keep at most k occurrences
In-place: O(1) space required
Single pass scan (no need to find boundaries or swap from both ends)
Lookback check: `num > nums[idx - k]` instead of element-by-element comparison
Anti-Signals:
- Unsorted array → requires hashing or sorting first
- Need to preserve absolute order of all elements (not just unique ones) → different problem
- Multiple different elements to remove (not duplicates of the same element) → reach for partition patterns
- Stable removal order matters → two-pointer swap may not guarantee order
  Decision Point: Sorted array + remove duplicates (or allow k occurrences)? → single-pass lookback window. The condition idx < k || num > nums[idx − k] elegantly handles both the bootstrap phase and the steady-state comparison.
  Interviewer Comms: “Since the array is sorted, I can identify unique elements in a single pass. I maintain a slot index that tracks where the next unique element should go. For each element, I check: if I haven’t yet seen k elements (idx < k), I accept it; otherwise, I compare the current element with the element k positions back. If they differ, it’s new. This generalises: k=1 removes all duplicates, k=2 allows each value twice. Time is O(n), space is O(1).”

Pitfalls and Misconceptions

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Trap: Compare current element with the immediate previous element (`num != nums[idx - 1]`) instead of the lookback (`num > nums[idx - k]`). Why: For k=1, this works. But it doesn’t generalise: when you want to allow k occurrences, you need to compare against the element k positions back, not just the immediate predecessor. Correction: Use the lookback condition `idx < k or num > nums[idx - k]`. This properly handles both the bootstrap (idx < k) and the repeated-occurrence detection (num > nums[idx − k]).
Trap: Forget the bootstrap condition `idx < k` and only check `num > nums[idx - k]`. Why: In the first k iterations, idx − k is negative or out-of-bounds. If you only check the lookback, you’ll miss the first k elements or hit an index error. Correction: Always guard with `idx < k` first. This allows the first k elements to be unconditionally accepted, then switch to lookback mode.
Trap: Treat the slot (idx) as the result size without incrementing it. Why: idx should track where the next unique element goes. If you don’t increment idx when you find a unique, you’ll overwrite the same position repeatedly. Correction: Increment idx every time you place an element: `nums[idx] = num; idx += 1`.
Trap: Use `<` instead of `<=` in `idx < k` or confuse the boundary. Why: Off-by-one. The first k elements have indices 0, 1, …, k−1. When idx = k, we’ve already placed k elements and should switch to lookback mode. Correction: `idx < k` captures indices 0 to k−1 (exactly k positions).
Trap: Forget to return idx and instead return k or n. Why: idx tracks the number of unique elements placed, not the parameter k or array length. Returning k or n will be wrong. Correction: Return idx, which is the count of unique (or “keep-up-to-k”) elements placed.

Problem Mutations

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

What if k=2 (allow at most 2 occurrences of each value)? (stress-test: generality) The algorithm is identical; only k changes. This is LC 80. The lookback condition num > nums[idx − 2] ensures at most 2 of the same value are kept.
What if the array is unsorted? (stress-test: assumption) Sorting first then applying this algorithm is O(n log n). Alternatively, use a hash set to track seen elements (O(n) time, O(n) space). The lookback pattern relies on sorted order and breaks on unsorted arrays.
What if we need to find k, i.e., what is the maximum number of times an element appears in the result? (stress-test: output change) Track frequency while placing elements. Count occurrences of each unique value in the result array.
What if the array is reverse-sorted instead of ascending? (stress-test: order) The lookback check num > nums[idx − k] breaks for descending order. Use num < nums[idx − k] instead, or reverse the array, apply the algorithm, then reverse back.
What if we need to remove duplicates but also track which elements were removed? (stress-test: side-effect tracking) Maintain a separate list of removed indices or values. The core algorithm placement logic remains the same; only the output changes.

Remove Duplicates from Sorted Array II (80)

Just have to comb through everything

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
   class Solution:
       def removeDuplicates(self, nums: List[int]) -> int:
           idx = 0
           k = 2
           for num in nums:
               # found unique:
               if idx < k or num > nums[idx - k]:
                   nums[idx] = num
                   idx += 1

           return idx

Code Snippet 3: Using the generalised form for Remove Duplicates from Sorted Array (80)

Pattern Extraction

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Core Insight: A generalisation of LC 26 (Remove Duplicates): instead of keeping one occurrence, keep at most k (here, k=2). Use a single-pass lookback window: accept an element if we haven’t yet placed k elements, or if it differs from the element k positions back.

Pattern Name: Sorted Array De-duplication with Bounded Occurrences (k-allowing window)

Canonical Section: Array Manipulation > Two-Pointer In-Place / Sorted Array Patterns

Recognition Signals:

Sorted array
Allow at most k occurrences of each value (k ≥ 1)
In-place modification, O(1) space
Single-pass scan sufficient
Generalised form: `idx < k or num > nums[idx - k]`
Anti-Signals:
- Unordered array → sort first or use different approach
- Variable k per element → different problem structure
- Preserve all elements but mark duplicates → separate tracking needed
- Exact number of occurrences required (not “at most k”) → counting problem, not removal
  Decision Point: Sorted array + allow ≤ k occurrences? → single-pass lookback with condition `idx < k or num > nums[idx - k]`. This is a direct instantiation of the generalised de-duplication pattern with k=2.
  Interviewer Comms: “This is a generalisation of removing duplicates. Instead of keeping one occurrence, I keep at most two. I use the same lookback window pattern: maintain a slot index (idx) for placement. For each element, if I haven’t yet placed 2 elements (idx < 2), accept it; otherwise, compare with the element 2 positions back. If they differ, it’s a new occurrence. Time is O(n), space is O(1).”

Pitfalls and Misconceptions

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Trap: Hardcode the condition `idx < 2 or num > nums[idx - 2]` without recognising it as a special case of the general `idx < k or num > nums[idx - k]` pattern. Why: Makes the solution specific to k=2 and unrecognisable for other k values. Blocks transfer learning to LC 26 (k=1) or future problems with different k. Correction: Name k explicitly (`k = 2`) at the top, then write the generalised condition. This clarifies the pattern and enables quick adaptation.
Trap: Use `nums[idx - 2] != num` instead of `nums[idx - 2] < num` or reverse the comparison. Why: For sorted ascending arrays, we’re checking if the current element is strictly greater than the element 2 positions back (since if they’re equal, we’ve seen this value at least twice). Reversing the check breaks the logic. Correction: Use `num > nums[idx - 2]` for ascending arrays. This correctly identifies “a new occurrence” as one that differs from the lookback point.
Trap: Forget the `idx < k` bootstrap guard and directly check `num > nums[idx - k]` on the first few iterations. Why: When idx < k, nums[idx - k] is invalid (out-of-bounds or wrong semantics). The first k elements must be unconditionally accepted. Correction: Always use the guard: `idx < k or num > nums[idx - k]`.
Trap: Not increment idx after placing an element, or increment conditionally. Why: idx tracks the placement position and the count of accepted elements. Every accepted element must increment idx once. Forgetting or conditional incrementing breaks the count and causes overwrites. Correction: Always increment idx after `nums[idx] = num; idx += 1`.
Trap: Return k (the occurrence limit) or n (array length) instead of idx. Why: k=2 is the parameter; n is the input size; idx is the count of elements in the result. Returning the wrong value gives the wrong answer size. Correction: Return idx, which is the size of the valid prefix.

Problem Mutations

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

What if k=3 (allow at most 3 occurrences)? (stress-test: parameter generalisation) Change `k = 2` to `k = 3` and the algorithm remains identical. Condition becomes `idx < 3 or num > nums[idx - 3]`. This confirms the generalisation works.
What if k=1 (remove all duplicates, exactly LC 26)? (stress-test: boundary case) Set k=1. Condition becomes `idx < 1 or num > nums[idx - 1]`, which simplifies to `idx == 0 or num > nums[idx - 1]`. This is the classic “different from immediate predecessor” pattern. Algorithm works.
What if the array has all identical elements (e.g., [1,1,1,1,1] with k=2)? (stress-test: worst case) First iteration (idx=0): idx < 2, accept. Second iteration (idx=1): idx < 2, accept. Third iteration (idx=2): nums[2]=1, nums[0]=1, 1 > 1? No, skip. Remaining iterations also skip. Result: [1, 1, _, _, _], return 2. Correct.
What if the array is reverse-sorted (e.g., [5,4,3,2,1])? (stress-test: order assumption) The lookback condition `num > nums[idx - k]` assumes ascending order. For descending, elements after the first k are always smaller, so all future comparisons fail. Use `num < nums[idx - k]` for descending, or reverse the input/output.
What if we need to track which indices had duplicates removed? (stress-test: side-effect) Maintain a separate removed-indices list while applying the core algorithm. For each num that fails the condition `idx < k or num > nums[idx - k]`, record its original index before skipping it. Core logic unchanged.

Squeeze/Converging Pointers Pattern: 2 pointers from opposite ends #

Two pointers start at opposite ends and move inward. Typically, this exploits some greedy property as well.

Typical use cases:
- Finding pairs that satisfy some condition (e.g., sum equals target).
- Sorting-related problems like partitioning or arranging.
- Examples:
  - Valid Palindrome.

Problems #

Two Sum II - Input Array Is Sorted (167)

We exploit the monotonicity from the sorting and squeeze two pointers from left and right, adjusting them greedily based on our target value that we’re searching for.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
         class Solution:
         def twoSum(self, numbers: List[int], target: int) -> List[int]:
             left, right = 0, len(numbers) - 1
             while left < right:
                 current_sum = numbers[left] + numbers[right]
                 if current_sum == target:
                     return [left + 1, right + 1]
                 elif current_sum < target:
                     left += 1
                 else:
                     right -= 1

Code Snippet 4: Two Sum II - Input Array Is Sorted (167)

Pattern Extraction

Core Insight: In a sorted array, two converging pointers exploit monotonicity: if the sum is too large, shrink from the right; if too small, grow from the left. This eliminates half the search space each step. Pattern Name: Sorted Two-Pointer Squeeze Canonical Section: Two Pointers > Converging Pointers Recognition Signals:

Sorted input (or sortable without losing information)
Find a pair satisfying a target condition (sum, difference, product)
$O(n)$ time, $O(1)$ space required
Exactly one solution guaranteed (simplifies termination)

Anti-Signals:

Unsorted input where sorting loses position information (need original indices) — use hash map instead
Finding ALL pairs, not just one — still works but need to handle duplicates carefully
Three or more elements — need to nest: fix one, two-pointer on the rest (LC 15 3Sum)

Decision Point: Sorted + pair finding = two-pointer squeeze. Unsorted + pair finding = hash map. The sort status of the input is the discriminator.

Pitfalls and Misconceptions

Trap: Using a hash map on a sorted array. Why: Works but wastes the sorted property. $O(n)$ space instead of $O(1)$. Correction: Two pointers on a sorted array gives $O(n)$ time, $O(1)$ space.
1. Trap: Returning 0-indexed results when the problem asks for 1-indexed.
Why: This specific problem uses 1-based indexing. Off-by-one in the return value. Correction: Return [left + 1, right + 1].

Problem Mutations

What if there could be multiple valid pairs? (stress-tests: unique solution assumption) Skip duplicates after finding a pair: advance both pointers past equal values. Connects to LC 15 3Sum deduplication logic.
What if the target were a difference instead of a sum? (stress-tests: operation type) Two pointers still work but both move from the left (not converging). If nums[right] - nums[left] is too small, advance right; if too large, advance left.
What if the array were unsorted and you couldn’t sort it? (stress-tests: sorted assumption) Fall back to hash map approach: store seen values and check for target - num. This is the original LC 1 Two Sum.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Two Sum II - Input Array Is Sorted generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

3-Sum (15)

In 3-Sum, the ideal approach is to do a sorting and then exploit the ordering properties. So we fix a single value, then we find its 2 complements based on that single value. Using a converging pointers approach for the 2-sum problem (sorted) saves space (instead of using aux datastructures here).

Specifically, the key idea here is that we just want to find a,b,c and to do that we have to fix a and find the pairs b,c. So the 2-pointer 2 sum approach works great here. From the previous experiences on running 2-sum on sorted (non-decreasing) arrays will give the intuition to pre-process (sort) the input array (in-place) first.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
         class Solution:
             def threeSum(self, nums: List[int]) -> List[List[int]]:
                 triplets = set()
                 n = len(nums)
                 nums.sort()  # Sorting helps with duplicate handling

                 for i in range(n): # candidate for the first value
                     # Skip duplicate 'a' values
                     canSkipDuplicate = i > 0 and nums[i] == nums[i - 1]
                     if canSkipDuplicate:
                         continue
                     # reset the seen set for each first num candidate
                     seen = set()
                     for j in range(i + 1, n):
                         complement = -nums[i] - nums[j]
                         if complement in seen:
                             # Found a triplet, add as a sorted tuple to avoid duplicates
                             # these are added as sorted tuples
                             triplet = tuple(sorted((nums[i], nums[j], complement)))
                             triplets.add(triplet)
                             seen.add(nums[j])

                 # Convert set of tuples back to list of lists
                 return [list(triplet) for triplet in triplets]

Code Snippet 5: 3-Sum (15)

Pattern Extraction

Core Insight: Fix one element, then reduce to sorted two-sum on the remaining subarray. Sorting enables both the two-pointer squeeze and duplicate skipping. Pattern Name: N-Sum Reduction (fix one, solve N-1) Canonical Section: Two Pointers > Converging Pointers Recognition Signals:

Find all unique triplets (or k-tuples) summing to a target
“No duplicate triplets” constraint
Input can be sorted without losing needed information

Anti-Signals:

Need to return indices, not values — sorting scrambles indices; use hash map approach
Very large $k$ (4Sum, 5Sum) — recursive N-Sum reduction or hash-based approach
Counting triplets rather than enumerating — may use mathematical shortcuts

Decision Point: “All unique triplets summing to zero” is the canonical 3Sum trigger. Sort first, then iterate + two-pointer. The duplicate-skipping logic (skip repeated a values, skip repeated b/c values) is the implementation crux.

Pitfalls and Misconceptions

Trap: Using a set of tuples for deduplication instead of in-line duplicate skipping. Why: Works but is slower ($O(n)$ hashing per tuple) and uses more space. The sorted array enables $O(1)$ duplicate skipping. Correction: After finding a valid triplet, advance both left and right past duplicates: while left < right and nums[left] = nums[left-1]: left += 1=.
Trap: Not sorting the array before applying two pointers. Why: Without sorting, two-pointer squeeze doesn’t work (can’t reason about sum magnitude from pointer positions). Correction: Always sort first. $O(n \log n)$ sort is dominated by the $O(n^2)$ outer loop anyway.
Trap: Skipping the first element duplicate check but not the inner loop duplicates (or vice versa). Why: Both levels need deduplication. Missing either produces duplicate triplets. Correction: Skip duplicates for the fixed element AND for the two-pointer pair.

Problem Mutations

What if you needed 4Sum instead of 3Sum? (stress-tests: k-value) Fix one more element, reduce to 3Sum. Generalises to k-Sum by recursive reduction. Connects to LC 18 4Sum.
What if you needed to count triplets instead of enumerate them? (stress-tests: output type) Sorting + two pointers still works, but count the number of valid pairs for each fixed element rather than collecting them. Can be faster if duplicates are common.
What if the target were not zero? (stress-tests: target value) Identical algorithm, just search for target - nums[i] in the two-pointer phase instead of -nums[i]. The target value doesn’t change the approach.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for 3Sum generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Container with the Most Water (11)

This is like a rubberband/clingwrap mental model. We should have the following Greedy Insight:
- At each step, we greedily discard the shorter wall, because keeping it can’t possibly help us form a larger area in the future.
Moving the taller line inward can’t increase the area because the width shrinks and the height can’t increase. This is because the shorter line is the bottleneck.
If we move the shorter line, we might find a taller line that might have more pros-than-cons-of-moving
So we should move the pointer that is pointing to the shorter line and move it inwards (to the center of the array).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
   class Solution:
       def maxArea(self, height: List[int]) -> int:

           left, right = 0, len(height) - 1
           max_area = 0

           # greedily explore using 2 pointers:
           while left < right:
               curr_area = (right - left) * min(height[left], height[right])
               max_area = max(max_area, curr_area)
               # we always try to go for the best current step. current step is limited by the smaller one, so we try to pick a bigger guy for it.
               # find the limiting factor and adjust:
               if height[left] < height[right]:
                   left += 1
               else:
                   right -= 1

           return max_area

Code Snippet 6: Container with the Most Water (11)

Pattern Extraction

Core Insight: The shorter wall is the bottleneck: moving the taller wall inward can only shrink the area (width decreases, height can’t increase), so always move the shorter wall to potentially find a taller one. Pattern Name: Greedy Converging Pointers (bottleneck elimination) Canonical Section: Two Pointers > Converging Pointers Recognition Signals:

Area/volume defined by two boundaries and the gap between them
Optimise over all pairs of boundaries
$O(n)$ time required (rules out $O(n^2)$ brute force)
The contribution of a pair is determined by the weaker/shorter element (min-bottleneck)

Anti-Signals:

The contribution depends on both elements equally (not a min-bottleneck) — greedy pointer movement isn’t justified
Need to find all optimal pairs, not just the maximum — can’t prune with greedy argument
Elements between the two boundaries also matter (like LC 42 Trapping Rain Water) — different problem

Decision Point: Container With Most Water asks about water held between two lines (max area of a rectangle). Trapping Rain Water asks about water held above all bars (sum of trapped water at each position). Same array, completely different problem structure.

Pitfalls and Misconceptions

Trap: Confusing this with Trapping Rain Water (LC 42). Why: Both involve heights and water, but Container asks for the max area between two lines while Trapping asks for total water above all bars. The algorithms are completely different. Correction: Container = max rectangle area = converging pointers with greedy elimination. Trapping = sum per-position water = prefix-suffix maxes or monotonic stack.
Trap: Moving the taller pointer instead of the shorter one. Why: Moving the taller pointer can’t increase the area: the height is still capped by the shorter wall, and the width decreases. Correction: Always move the shorter pointer. When heights are equal, moving either is fine (both lose width but might gain height).

Problem Mutations

What if heights could be negative? (stress-tests: non-negative assumption) Area calculation breaks — min(h[l], h[r]) * (r - l) can be negative. Would need to redefine the problem (absolute values? only positive pairs?).
What if you needed the top-K largest containers? (stress-tests: single-answer assumption) Greedy pointer movement can’t guarantee visiting all top-K pairs. Would need a priority-queue-based approach or a different pruning strategy.
What if the problem were 3D (finding the largest box volume among triples)? (stress-tests: dimensionality) Converging pointers don’t generalise to 3+ dimensions. Would need $O(n^2)$ with sorting or other techniques.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Container with the Most Water generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Valid Palindrome (125)

This is a good example of how there’s no ordering, but it’s the ordering that we do need to test. For this question, just keep in mind that we might to skip characters that don’t apply (non alnum and so on).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
   # typical O(n) time and O(1) space complexity
         class Solution:
             def isPalindrome(self, 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

         # NOTE: we could also opt for a slower method that does a char filtering, but it's not optimised
         # Runs in O(n) time and O(n) space.
         class Solution:
             def isPalindrome(self, s: str) -> bool:
                 filtered = [c.lower() for c in s if c.isalnum()]
                 return filtered == filtered[::-1]

Code Snippet 7: Valid Palindrome (125)

Pattern Extraction

Core Insight: A palindrome reads the same forwards and backwards; two pointers from opposite ends comparing inward is the natural $O(1)$-space check. Skip non-alphanumeric characters without materialising a filtered copy. Pattern Name: Two-Pointer Palindrome Verification Canonical Section: Two Pointers > Converging Pointers Recognition Signals:

“Is X a palindrome” or “check if string reads same forwards/backwards”
Need to ignore certain characters (non-alphanumeric, spaces, punctuation)
$O(1)$ space preferred (rules out creating a filtered copy)

Anti-Signals:

“Longest palindromic substring” — interval DP or expand-around-center, not just verification
“Make X a palindrome with minimum insertions” — DP problem, not two-pointer
“Count palindromic substrings” — Manacher’s or DP, not simple verification

Decision Point: Verification (boolean) = two-pointer. Optimisation (longest/shortest/count) = DP or expand-around-center.

Pitfalls and Misconceptions

Trap: Creating a filtered, lowercased copy of the string and then checking with s = s[::-1]=.

Why: Works but uses $O(n)$ space. The two-pointer approach achieves $O(1)$ space. Correction: Skip non-alphanumeric characters in-place with while loops advancing each pointer.

Trap: Forgetting to normalise case — comparing 'A' and 'a' as different.

Why: Palindrome checks are case-insensitive. Missing .lower() causes false negatives. Correction: Compare s[left].lower() = s[right].lower()=.

Problem Mutations

What if you could delete at most one character to make it a palindrome? (stress-tests: exact match assumption)

When a mismatch is found at (l, r), check if either s[l+1:r+1] or s[l:r] is a palindrome. Connects to LC 680 Valid Palindrome II.

What if you needed the minimum deletions to make it a palindrome? (stress-tests: single deletion)

Minimum deletions = n - LPS(s) where LPS is Longest Palindromic Subsequence. This is a 2D DP problem. Connects to LC 516 Longest Palindromic Subsequence.

What if the string were a linked list? (stress-tests: random access assumption)

Reverse the second half using slow/fast pointer to find the middle, then compare. Connects to LC 234 Palindrome Linked List.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Valid Palindrome generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Trapping Rainwater (42) ⭐️

We ask ourselves how water gets trapped and we realise that we need to find valleys. So we need to keep track of a max left and max right (heights) for each index we see because the amount of water trapped depends on the best height to the right and the best height to the left $\implies$ how deep the valley is. This is the key guiding characteristic for this question.
This gives us the greedy observation that we should shift the limiting pointer (the one that is shorter of the two [right, left])

Actually this question also has other approaches we can consider as well, typically all of the following approaches should work well:

converging pointers solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
        # M1: converging pointers solution (optimal) O(n) time, O(1) space
        class Solution:
            def trap(self, height: List[int]) -> int:
                if not height:
                    return

                left, right = 0, len(height) - 1
                max_left, max_right = height[left], height[right]

                accum = 0

                while left < right:
                    # if left is shorter, then instead of the right boundary, this is the one that is limiting it
                    if is_left_shorter:=(max_left < max_right):
                        left += 1 # we compare the immediate next to the limited boundary:
                        max_left = max(max_left, height[left])
                        valley_depth = max_left - height[left]
                        accum += max(valley_depth, 0)
                    else:
                        # mirror
                        right -= 1 # compare the immediate
                        max_right = max(max_right, height[right])
                        valley_depth = max_right - height[right]
                        accum += max(valley_depth, 0)

                return accum

Code Snippet 8: Trapping Rainwater (42) – converging pointers solution optimal $O(n)$ time, $O(1)$ space

stack based approach (but not optimal in its use of space). We use stack to keep track of all the “next greater than"s

stack keeps indices of bar heights that haven’t found a taller bar to the right

when encountering a bar taller than the bar at the idx stored at the top of the stack ==> we can trap water above the bar represented by that index

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
                        # M2: Stack based approach O(n) time, O(n) space
                        class Solution:
                            def trap(self, height):
                            if not height:
                                return 0

                            n = len(height)
                            trapped_water = 0
                            stack = []

                            for i in range(n):
                                # While there are indices in stack and current height is
                                # greater than height at index stored on top of stack
                                while stack and height[i] > height[stack[-1]]:
                                    top = stack.pop()  # Get index of top element

                                    if not stack:  # If stack is empty after popping
                                        break

                                    # Calculate width
                                    width = i - stack[-1] - 1
                                    # Calculate bounded height
                                    bounded_height = min(height[i], height[stack[-1]]) - height[top]
                                    # Update total trapped water
                                    trapped_water += width * bounded_height

                                # Push current index onto stack
                                stack.append(i)

                            return trapped_water

Code Snippet 9: Trapping Rainwater (42) – stack-based approach $O(n)$ time, $O(n)$ space

prefix-sum approach: this is like the converging pointers solution but without the O(1) space optimisation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
                      # M3: Prefix Sum approach O(n) time, O(n) space
        class Solution:
            def trap(self, height: List[int]) -> int:
                if not height:
                    return

                n = len(height)
                left_maxes, right_maxes = [0] * n, [0] * n

                for i in range(n):
                    prev_max = left_maxes[i - 1] if i - 1 >= 0 else 0
                    left_maxes[i] =  max(prev_max, height[i])

                # right maxes, we accumulate from right to left
                for i in range(n - 1, - 1, -1):
                    next_max = right_maxes[i + 1] if i + 1 < n else 0
                    right_maxes[i] = max(next_max, height[i])

                accum = 0

                for idx, (left_max, right_max) in enumerate(zip(left_maxes, right_maxes)):
                    valley_height = height[idx]
                    limiting = min(left_max, right_max)
                    accum += limiting - valley_height

                return accum

Code Snippet 10: Trapping Rainwater (42) – prefix-sum solution $O(n)$ time, $O(n)$ space

Fast and Slow pointers: 2 pointers moving in the same direction #

tortoise hare fashion: one ptr moves faster than the other. Faster pointer can process / filter data on the fly. It’s a lookahead. It’s typically more useful for linked list scenarios though.

Problems #

check out cycle detection problems here,
- Detecting cycles in linked lists is usually something we try to use floy’d tortoise and hare method for.
- extra: realise that tortoise and hare method can be applied in abstract fashions as well. Consider the Happy Number problem within number theory computations
removing duplicates/filtering elements from a collection that has some ordering

Sliding window: variable sized window b/w 2 pointers #

two pointers define the sliding window, refer to the sliding window category of problems. The two pointers demarcate contiguous regions.

Generally Used for:
- Finding longest/shortest substring/subarray fulfilling criteria.
- Counting number of valid substrings/subarrays.
- Examples: Longest substring without repeating characters, Minimum Window Substring, look within the sliding window section to find out more.

Partitioning / Grouping Problems #

Using pointers to divide data into (contiguous) regions based on some properties.
Common in sorting (e.g., Dutch National Flag problem).
Also useful in problems requiring in-place rearrangement.

Problems #

Number of Perfect Pairs (3649)

The key realisation here is “what is i and j referring to”. It can refer to the abs sorted array, as long as we are consistent.

from analysing the conditions, we observer that we need to find bs for every a such that $|b|∈ [ |a|, 2|a|]$, so the problem is rephrased into: “for every a, count how many elements b satisfy $|a| \leq |b| \leq 2|a|$”

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
    class Solution:
       def perfectPairs(self, nums: List[int]) -> int:
           """
           when choosing i, j we can make it with reference to the sorted abs array actually, as long as it's consistent. That's the key takeaway here.

           so we need to find bs for as where b is within [a, 2a]
           """
           abs_nums = sorted(abs(x) for x in nums)
           n = len(abs_nums)
           ans = 0

           j = 0 # idx representing values of b
           for i in range(n): # for idx representing every a
               # find the largest j such that it still meets the conditions. Shift J until condition is no longer met
               while j < n and abs_nums[j] <= 2 * abs_nums[i]:
                   j += 1
                   # Count number of bs where abs(b) >= abs(a)
                   # Since array is sorted, bs start from i+1 to j - 1
               if j > i + 1:
                   ans += j - i - 1

           return ans

Code Snippet 11: Number of Perfect Pairs (3649)

Pattern Extraction

Core Insight: When pair validity depends on a property computable from sorted order (e.g., bitwise OR/AND conditions on sorted values), sort the absolute values and use two pointers or binary search to count valid pairs. Pattern Name: Sort + Two-Pointer Pair Counting Canonical Section: Two Pointers > Partitioning / Grouping Recognition Signals:

Count pairs $(i, j)$ satisfying some condition
Condition is symmetric or can be checked on sorted data
$O(n^2)$ brute force too slow; need $O(n \log n)$

Anti-Signals:

Pair condition depends on original positions (not sortable)
Need the actual pairs, not just the count — sorting loses index info
Condition involves three or more elements — two-pointer pair counting doesn’t extend directly Decision Point: If the pair condition is order-invariant (depends on values, not positions), sort first. If it depends on positions, use hash map or prefix structures.

Pitfalls and Misconceptions

Trap: Brute-forcing all pairs in $O(n^2)$.

Why: Too slow for large $n$. The sorted structure enables pruning. Correction: Sort the relevant values and use two pointers or binary search to count valid pairs in $O(n \log n)$.

Trap: Confusing what i and j refer to when the array is sorted. Why: After sorting, indices refer to sorted positions, not original positions. If the pair condition is on values only, this is fine; if on original indices, sorting breaks the problem. Correction: Verify that the pair condition is position-independent before sorting.

Problem Mutations

What if the pair condition involved XOR instead of OR/AND? (stress-tests: bitwise operation type)

XOR doesn’t have the monotonicity properties that AND/OR have on sorted data. Two-pointer approach may not work; consider trie-based approaches instead. Connects to LC 421 Maximum XOR.

What if you needed the count modulo $10^9 + 7$? (stress-tests: overflow) The counting logic is identical; just take modulo at each addition step. Modular arithmetic commutes with addition.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Number of Perfect Pairs generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Merging / Comparing 2 Sorted Arrays / Sequences #

two pointers, tracks positions in different arrays to do the job (merge / find intersections)
Examples: Merge Sorted Arrays, Intersection of Two Arrays.

Problems #

Intersection of Two Arrays (349)

We sort the two arrays, then we advance two pointers, one in each array. We greedily make decisions, moving the pointer that points to the smaller value each time.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
      class Solution:
          def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
              nums1.sort()
              nums2.sort()
              i = j = 0
              result = set()
              while i < len(nums1) and j < len(nums2):
                  if nums1[i] == nums2[j]:
                      result.add(nums1[i])
                      i += 1
                      j += 1

                  elif nums1[i] < nums2[j]:
                      i += 1
                  else:
                      j += 1

              return list(result)

Code Snippet 12: Intersection of Two Arrays (349)

Pattern Extraction

Core Insight: Intersection of two collections is a set operation; convert both to sets and use set intersection. If sorted, two pointers advancing past smaller values achieves $O(1)$ space. Pattern Name: Two-Pointer Merge / Set Intersection Canonical Section: Two Pointers > Converging or Same-Direction Pointers Recognition Signals:

“Elements in common” between two collections
Output should have unique elements (set semantics)
If already sorted: two-pointer merge pattern
If unsorted: hash set intersection

Anti-Signals:

Need to preserve duplicates (intersection with multiplicity) — use Counter instead of set. Connects to LC 350 Intersection of Two Arrays II
Need the union, not intersection — different set operation

Decision Point: Unique intersection = set. Intersection with counts = Counter or sorted merge with duplicate tracking. Sorted input = two-pointer; unsorted = hash set.

Pitfalls and Misconceptions

Trap: Using nested loops for intersection ($O(mn)$). Why: Inefficient when hash-based intersection is $O(m + n)$. Correction: set(nums1) & set(nums2) in Python, or two pointers if sorted.
Trap: Not handling the “unique elements” requirement when using two pointers on sorted arrays. Why: Sorted arrays can have duplicates; the two-pointer merge will emit the same element multiple times. Correction: Skip duplicates in both arrays after each match.

Problem Mutations

What if you needed intersection with multiplicity (each element appears min(count1, count2) times)? (stress-tests: uniqueness assumption) Use collections.Counter and take element-wise minimum. Connects to LC 350 Intersection of Two Arrays II.
What if the arrays were sorted and one was much larger than the other? (stress-tests: equal size assumption) Binary search the smaller array’s elements in the larger one: $O(m \log n)$ where $m \ll n$. Better than $O(m + n)$ merge.
What if the arrays were streams? (stress-tests: static assumption) Need an online data structure. Maintain a hash set of seen elements from one stream; check membership as elements arrive from the other.

AI usage disclosure Claude Opus 4.6 · content enrichment

Standardised annotation dropdowns for Intersection of Two Arrays generated via batch canonical enrichment pass. Review against personal solving experience and adjust.

Merge Sorted Array (88)

This one is an essential, it requires us to realise that the empty space needs to be used and we can merge in reverse order to keep things in-place:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
   class Solution:
       def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
           """
           This involves merging from the back
           """
           p1, p2 = m - 1, n - 1
           p = (m + n) - 1 # write slot, writes to here from the back

           while p1 >= 0 and p2 >= 0:
               if nums1[p1] >= nums2[p2]:
                   nums1[p] = nums1[p1]
                   p1 -= 1

               else:
                   nums1[p] = nums2[p2]
                   p2 -= 1
                   # new write slot:
               p -= 1

           # if we still have things in nums2:
           while p2 >= 0:
               nums1[p] = nums2[p2]
               p2 -= 1
               p -= 1

Code Snippet 13: Merge Sorted Array (88) - 2 pointers, fill in reverse.

Pattern Extraction

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Core Insight: When merging into a destination array with surplus space, work backwards from the end to avoid overwriting unprocessed data. The unused tail of nums1 becomes the working space.

Pattern Name: Two-Pointer Backwards Merge

Canonical Section: Array Manipulation > In-Place Operations; or Two-Pointer Techniques > Merge

Recognition Signals:

Merge two sorted arrays with one array in-place
Destination array has surplus space at the end (tail padding with 0s)
Cannot use auxiliary array; O(1) space constraint
Both arrays are pre-sorted (monotonicity)
Anti-Signals:
- Merge with no surplus space → use insertion or auxiliary array
- Unordered arrays → sort first or use hash-based merge
- Merge into new array (space available) → standard left-to-right merge is simpler
- Need to preserve originals → create copy, then merge
  Decision Point: In-place merge + surplus space at end of destination? → backwards iteration. Without surplus space, the problem becomes O((m+n)²) or requires auxiliary storage.
  Interviewer Comms: “This is merging two sorted arrays in-place. The key is that nums1 has reserved space at the end for exactly m + n elements. I’ll use three pointers: one at the end of nums1’s valid data, one at the end of nums2, and one at the end of nums1’s total space. I compare the two tail elements, place the larger one at the target tail position, and move backwards. When nums2 is exhausted, nums1’s remaining elements are already in place. This is O(m+n) time and O(1) space.”

Pitfalls and Misconceptions

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

Trap: Merge left-to-right into nums1 by shifting elements right to make space. Why: This is the intuitive approach (fill the beginning of the result first), but requires O(m+n) shifts per element, totalling O((m+n)²) time. Also, it’s easy to overwrite nums1 data before copying it to nums2. Correction: Don’t merge left-to-right. Use the empty space at the end: work backwards from position m+n−1, comparing tail elements and placing the larger one, moving both pointers down.
Trap: Forget to handle the case where nums2 is not fully consumed. Why: If nums1 is exhausted first (p1 < 0) but nums2 still has elements (p2 ≥ 0), those nums2 elements must be copied into nums1. If you skip this, the final positions in nums1 will be 0 or garbage. Correction: After the main two-pointer loop, check if p2 ≥ 0. If so, copy all remaining nums2[0:p2+1] into nums1’s remaining tail positions.
Trap: Forget that nums1’s remaining elements (when p1 ≥ 0 but p2 < 0) don’t need copying. Why: When nums2 is exhausted, nums1’s elements are already in their correct positions in nums1—no action needed. However, not recognising this can lead to unnecessary copying logic or confusion about what to do in the second while loop. Correction: The second loop checks p2 ≥ 0, not p1 ≥ 0. If p2 < 0, the loop doesn’t run, and nums1’s elements remain untouched (they’re already merged).
Trap: Use equality check (=) instead of (>) in the comparison, or confuse which branch takes which element. Why: If nums1[p1] = nums2[p2], the tie-break matters for stability. Using (>) is equivalent to the “take from nums2 on equality” convention, which matches the expected merge semantics. If you use (>=), you’d take from nums1 on equality, which is less conventional. Correction: Use `if nums1[p1] > nums2[p2]` to take from nums1; otherwise take from nums2. The “else” branch naturally handles equality and leaves-nums2-alone-if-nums1-tail-is-empty cases.
Trap: Confuse the pointer semantics: p1 should track the end of valid data in nums1, not the total space. Why: m is the count of valid elements in nums1, so p1 = m − 1 is the index of the last valid element. The tail space (indices m to m+n−1) is where merging happens. If you start p1 = 0 or p1 = m + n − 1, you’ll index out of bounds or process invalid data. Correction: p1 = m − 1 (last valid element in nums1), p2 = n − 1 (last element in nums2), p = m + n − 1 (target position in nums1’s full space).

Problem Mutations

AI usage disclosure Claude Sonnet 4.6 · coaching-annotation

This dropdown was generated during coaching. Verify before integrating.

What if nums2 is empty (n = 0)? (tests: edge case handling) Both loops exit immediately since p2 = −1 before entering. nums1 is unchanged, which is correct. The algorithm handles this gracefully without special-casing.
What if nums1 is empty (m = 0)? (tests: edge case handling) p1 = −1 before entering the loop, so the first loop condition p1 ≥ 0 is false immediately. The second loop then copies all of nums2 into nums1. Correct.
What if we need to merge into a separate array (not in-place)? (tests: space constraint) Use standard left-to-right two-pointer merge into a new result array. Simpler logic: compare and append, no need to worry about overwriting. Time remains O(m+n), space becomes O(m+n).
What if nums1 has no surplus space (total length = m, not m+n)? (stress-test: space) Impossible to solve in O(m+n) and O(1) space. Must either: (a) create auxiliary array (O(m+n) space), or (b) use in-place insertion/shift (O((m+n)²) time). This problem is only solvable efficiently because nums1 is pre-allocated.
What if the arrays are not sorted? (stress-test: assumption) Sort both first, then merge. Or merge and sort the result (defeats the purpose of the two-pointer merge). The backwards merge assumes monotonicity; violating it will produce an unsorted result.

Pair and Triplet Sum Problems #

Constraint satisfying sum / difference

Examples:

3Sum: $O(n^2)$ runtime, sort input, for every first idx (fix a), look for pairs b and c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            triplets = []
            n = len(nums)
            for first_idx in range(n):
                # can skip duplicates for first_idx
                if first_idx > 0  and nums[first_idx] == nums[first_idx - 1]:
                    continue

                # now, find 2 sum for target = complement:
                left, right = first_idx + 1, n - 1
                complement = -nums[first_idx]
                while left < right:
                    partial_sum = nums[left] + nums[right]
                    # case 1: found a triplet:
                    if partial_sum == complement:
                        triplets.append([nums[first_idx], nums[left], nums[right]])
                        # skip duplicates for the other pointers, as much as possible:
                        while(can_skip_duplicate_lefts:= left < right and nums[left] == nums[left + 1]):
                            left += 1
                        while(can_skip_duplicate_rights:= left < right and nums[right] == nums[right - 1]):
                            right -= 1

                        # converge pointer as per normal
                        left += 1
                        right -= 1

                    # case 2: need to move the left point to attempt to get a bigger sum:
                    elif (partial_sum < complement):
                        left += 1

                    # case 3: partial sum > complement, need to make the partial sum smaller, so we move the right pointer
                    else:
                        right -= 1

            return triplets

Code Snippet 14: Pair and Triplet Sum Problems

4Sum,

Closest Pair in Sorted Array.

Subsequence / Subarray Enumeration using 2 Pointers #

Find or count subsequences/subarrays matching criteria using dynamic left/right pointer movements.
Variants often overlap with sliding window.

SOE #

Not moving both pointers correctly
Remember to skip duplicates, also the search space matters
e.g. in 3-sum, the searching for b and c is always in the right side space of the current idx that we are looking at. This avoids double counting. We also avoid duplicates first_idx > 0 and nums[first_idx] = nums[first_idx - 1]=
different from stack based solutions
Infinite loops if pointers don’t converge

Decision Flow #

Sorted array? → 2-pointer worth using
this works because there’s a monotonic order which gives us good invariants to work with (e.g. if we want a smaller sum, we can shift right, if larger sum then we can shift left pointer…)
have to keep an eye on greedy decisions that can be made. e.g. container with most water: we greedy discard the shorter wall because keeping it can’t possibly help us to form a larger area in the future.
Substring window? → sliding window variant

2 pointers vs stack approaches: a comparative analysis #

Key insight: Local vs Contextual Resolution:
two pointers work with direct comparisons and boundaries, while stacks handle implicit nested relationships (contextual) in a sequential but flexible manner
for this, we can take the “trapping rainwater” problem as a didactic example.
Generic Mechanisms:
1. 2 pointer
  - uses indices moving inwards / along structure, making local decisions based on comparisons on both ends
  - the properties that are exploited are visible from 2 ends simultaneously
  - the two pointers are used to get a linear pass leveraging symmetry or monotonicity from both directions
2. stack approach
  - aux stack (typically monotonic), maintain structure of induces / values that upholds an invariant. This invariant helps to resolve dependencies / boundaries when considering new element.
  - so it captures ‘history’ / relationships that we can’t in a single linear pass
  - typically good for “next greater” / “previous smaller” element patterns.
Use cases:
- if the problem inherently has symmetric or boundary conditions you can exploit from both sides simultaneously $\rightarrow$ 2 pointer approach
- if you need to track and resolve nested, dependent, or previously-seen elements that affect current computations (e.g., nearest greater/smaller elements) $\implies$ (monotonic) stack-based approaches

Styles, Tricks and Boilerplate #

string stdlib functions can be useful e.g. "s".isalnum(), "s".isnumeric()

TRICK: for 2D arrays, we can pretend that it’s flattened and divmod will be useful. e.g. noticeable the use of the divmod in the code below!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
  class Solution:
      def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          if not matrix or not matrix[0]:
              return False

          m, n = len(matrix), len(matrix[0])
          left, right = 0, ( m * n ) - 1

          while left <= right:
              mid = (left + right) // 2
              # TRICK: ⭐️ this is pretty!
              row, col = divmod(mid, n)
              val = matrix[row][col]
              if val == target:
                  return True
              elif val < target:
                  left = mid + 1
              else:
                  right = mid - 1
          return False

Code Snippet 15: 2 pointers vs stack approaches: a comparative analysis

TODO KIV #

[ ] Dutch National Flag Algo #

[ ] Group together the family of container type problems #

some of the easier solutions form the building blocks to approach the harder ones.

e.g. the container with most water
e.g. trapping rainwater
e.g. max histogram

[ ] Undone canonicals #

See the canonical tables within each sub-section above for problem coverage. Additional problems to tackle are listed below.

opposite ends:
- 3 Sum Closest
- 4 Sum