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.

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 1: 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 2: 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 3: 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 4: 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 5: 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 6: 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 7: 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 8: 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 9: 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.

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 10: 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 11: 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
Merge Sorted Array (88)