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 #

1. 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

2. 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]

3. 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.

     1. 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.
     2. If we move the shorter line, we might find a taller line that might have more pros-than-cons-of-moving
     3. 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 19

        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

4. 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]

5. 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:

   1. converging pointers solution

   2. 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

   3. 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

      # 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 # M2: Stack based approach O(n) time, O(n) space # 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 # 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

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 #

1. 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

2. 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 section below on the sliding window category of problems. the two pointers demarcate contiguous regions.

TODO: fix “sliding window category” URL

• 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 #

1. 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

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 #

1. 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)

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

    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:

  • 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

    • used to get a linear pass leveraging symmetry or monotonicity from both directions

  • 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

  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

Style, Recipes, 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

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 (not including canonical tables) #

A comprehensive set of **two pointer** problems, especially on LeetCode, covers a wide range of array, string, and linked list tasks. These are typically classified into several canonical categories, with examples and direct LeetCode problem references provided below for each pattern.[1]

### Opposite Ends (Classic Two Pointers)
- Pointers start at both ends and converge.
- Typical use: Finding pairs, partitioning, array reversals.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Two Sum II - Input Array Is Sorted | Find two numbers adding to target in a sorted array | (https://leetcode.com/problems/two-sum-ii-input-array-is-sorted) |
| 3Sum | Find all unique triplets that sum to zero | [2](https://leetcode.com/problems/3sum) |
| 3Sum Closest | Find triplet sum closest to target | [3](https://leetcode.com/problems/3sum-closest) |
| 4Sum | Find all unique quadruplets that sum to target | [4](https://leetcode.com/problems/4sum) |
| Valid Palindrome | Check if string is palindrome (ignore case/non-alphanum) | (https://leetcode.com/problems/valid-palindrome) |

### Fast and Slow Pointers (Tortoise and Hare)
- One pointer advances faster; classic for cycle detection in lists.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Linked List Cycle | Detect cycle in linked list | (https://leetcode.com/problems/linked-list-cycle) |
| Linked List Cycle II | Find start of cycle in linked list | (https://leetcode.com/problems/linked-list-cycle-ii) |
| Middle of the Linked List | Find middle node | (https://leetcode.com/problems/middle-of-the-linked-list) |
| Remove Nth Node From End | Remove the nth node from end of list | [5](https://leetcode.com/problems/remove-nth-node-from-end-of-list) |

### Same Direction Pointers / Shrinking Window
- Both pointers move forward to maintain/adjust a window or segment.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Remove Duplicates from Sorted Array | Remove duplicates in-place | [1](https://leetcode.com/problems/remove-duplicates-from-sorted-array) |
| Remove Duplicates from Sorted Array II | Each element appears at most twice | (https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii) |
| Move Zeroes | Move all zeroes to end, in-place | (https://leetcode.com/problems/move-zeroes) |
| Remove Element | Remove all instances of val | [6](https://leetcode.com/problems/remove-element) |
| Backspace String Compare | Simulate backspaces, compare results | (https://leetcode.com/problems/backspace-string-compare) |

### Sliding Window - Fixed Size
- Maintain a window of constant size.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Sliding Window Maximum | Max in every window of size k | (https://leetcode.com/problems/sliding-window-maximum) |
| Maximum Average Subarray I | Max average of size k subarray | (https://leetcode.com/problems/maximum-average-subarray-i) |
| Grumpy Bookstore Owner | Max satisfied customers | (https://leetcode.com/problems/grumpy-bookstore-owner) |

### Sliding Window - Variable Size
- Dynamically expand/shrink window based on constraints.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Longest Substring Without Repeating Characters | Longest substring no repeats | [7](https://leetcode.com/problems/longest-substring-without-repeating-characters) |
| Minimum Window Substring | Smallest window with all chars | (https://leetcode.com/problems/minimum-window-substring) |
| Permutation in String | Check if string contains permutation | (https://leetcode.com/problems/permutation-in-string) |
| Find All Anagrams in a String | Start indices of anagrams | (https://leetcode.com/problems/find-all-anagrams-in-a-string) |
| Minimum Size Subarray Sum | Smallest subarray ≥ sum | (https://leetcode.com/problems/minimum-size-subarray-sum) |
| Longest Repeating Character Replacement | Max window with at-most k replacements | (https://leetcode.com/problems/longest-repeating-character-replacement) |

### Sorted Arrays / Merging / Intervals
- Merge, intersect, or process sorted sequences.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Boats to Save People | Min boats to carry weight pairs | (https://leetcode.com/problems/boats-to-save-people) |
| Squares of a Sorted Array | Return sorted squares of array | (https://leetcode.com/problems/squares-of-a-sorted-array) |
| Intersection of Two Arrays | Unique intersection values | (https://leetcode.com/problems/intersection-of-two-arrays) |
| Intersection of Two Arrays II | Counted intersection values | (https://leetcode.com/problems/intersection-of-two-arrays-ii) |
| Interval List Intersections | Overlap of two interval lists | (https://leetcode.com/problems/interval-list-intersections) |

### Advanced Variants and Miscellaneous
- Problems can use multiple pointers for searching, merging, or constraint checking.

| Problem | Description | LeetCode Link |
|---------|-------------|--------------|
| Trapping Rain Water | Compute total trapped water | (https://leetcode.com/problems/trapping-rain-water) |
| Merge Sorted Array | Merge two sorted arrays in-place | (https://leetcode.com/problems/merge-sorted-array) |
| Remove Duplicates from Sorted List | Linked list version, in-place | (https://leetcode.com/problems/remove-duplicates-from-sorted-list) |
| Merge Two Sorted Lists | Merge two sorted linked lists | [8](https://leetcode.com/problems/merge-two-sorted-lists) |

These examples are considered canonical for **interview prep** and algorithmic mastery. Each exhibits a classic two pointer strategy—either working from the outside in, together through a window, or manipulating multiple indices to maintain complex invariants.[1]

[1](https://www.scribd.com/document/875889681/LeetCode-TwoPointers-SlidingWindow-Patterns)
[2](https://www.youtube.com/watch?v=QzZ7nmouLTI)
[3](https://blog.algomaster.io/p/15-leetcode-patterns)
[4](https://www.youtube.com/watch?v=r_mVgmc89_U)
[5](https://www.linkedin.com/posts/shreshthi-badjatya_solved-all-two-pointers-problems-in-100-days-activity-7237766315657064450-prMq)
[6](https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/solutions/4302409/python-o-n-log-n-by-sorting-and-two-pointers-w-comment/)
[7](https://www.geeksforgeeks.org/dsa/top-problems-on-two-pointers-technique-for-interviews/)
[8](https://www.reddit.com/r/leetcode/comments/1bov6fw/two_pointer_problems_how_do_we_know_whether_to/)
[9](https://leetcode.com/problem-list/two-pointers/)
[10](https://www.reddit.com/r/leetcode/comments/18g9383/twopointer_technique_an_indepth_guide_concepts/)
[11](https://leetcode.com/discuss/post/1688903/Solved-all-two-pointers-problems-in-100-days/)
[12](https://leetcode.com/discuss/post/1688903/solved-all-two-pointers-problems-in-100-z56cn/)
[13](https://leetcode.com/problems/max-number-of-k-sum-pairs/discuss/2007103/two-pointer-approach)
[14](https://leetcode.com/discuss/study-guide/2546082/Leetcode-questions-for-SDE-Prep-for-FAANG(Links-are-topic-and-Difficulty-wise))
[15](https://leetcode.com/discuss/study-guide/6028247/Two-Pointers-TwoSums-3Sum-BST-Sum-4Sum-All-variations/)
[16](https://seanprashad.com/leetcode-patterns/)
[17](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/discuss/1436630/simple-solution-in-java-with-2-pointer-algorithm-in-on-time-complexity)
[18](https://www.designgurus.io/blog/top-lc-patterns)

• opposite ends:
  • 3 Sum Closest
  • 4 Sum
• Merge Sorted Array (88)