Two Pointer Patterns
Two Pointers - Converging (Sorted Array Target Sum)
5 practice problems
How to recall this pattern
If the input is sorted and you need a pair/sum — think left+right pointers converging inward. Move the smaller side up or the larger side down.Visual diagram
Theory
- Place one pointer at the start and one at the end of a sorted array.
- If the sum is too small, move the left pointer right. If too large, move the right pointer left.
- Works because sorting gives a monotonic relationship between pointer movement and sum.
- Time: O(n), Space: O(1). Requires sorted input or sort first in O(n log n).
Code template
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
curr = nums[left] + nums[right]
if curr == target:
return [left, right]
elif curr < target:
left += 1
else:
right -= 1
return [-1, -1]Practice problems · 5
Array is sorted. Start pointers at both ends. If sum < target, move left pointer right to increase sum. If sum > target, move right pointer left to decrease it. Return 1-indexed positions.
def twoSum(numbers, target):
l, r = 0, len(numbers) - 1
while l < r:
s = numbers[l] + numbers[r]
if s == target:
return [l + 1, r + 1]
elif s < target:
l += 1
else:
r -= 1Sort the array. Fix one number, then use converging two pointers on the rest to find pairs that sum to negative of the fixed number. Skip duplicates at every level to avoid duplicate triplets.
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == 0:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]: l += 1
while l < r and nums[r] == nums[r-1]: r -= 1
l += 1; r -= 1
elif s < 0: l += 1
else: r -= 1
return resSame two-pointer approach as 3Sum but instead of looking for exactly 0 we track whichever sum is closest to target. If we hit target exactly, return immediately.
def threeSumClosest(nums, target):
nums.sort()
closest = float('inf')
for i in range(len(nums) - 2):
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if abs(s - target) < abs(closest - target):
closest = s
if s < target: l += 1
elif s > target: r -= 1
else: return s
return closestExtend 3Sum by adding one more outer loop. Fix two numbers with nested loops, then converge two pointers for the remaining pair. Skip duplicates at each level.
def fourSum(nums, target):
nums.sort()
res = []
for i in range(len(nums) - 3):
if i > 0 and nums[i] == nums[i-1]: continue
for j in range(i+1, len(nums) - 2):
if j > i+1 and nums[j] == nums[j-1]: continue
l, r = j + 1, len(nums) - 1
while l < r:
s = nums[i]+nums[j]+nums[l]+nums[r]
if s == target:
res.append([nums[i],nums[j],nums[l],nums[r]])
while l<r and nums[l]==nums[l+1]: l+=1
while l<r and nums[r]==nums[r-1]: r-=1
l+=1; r-=1
elif s < target: l+=1
else: r-=1
return resTraverse the BST (DFS or BFS). For each node, check if complement (k - node.val) exists in a set. If yes, found the pair. Otherwise add current value to set and continue.
def findTarget(root, k):
seen = set()
stack = [root]
while stack:
node = stack.pop()
if not node: continue
if k - node.val in seen:
return True
seen.add(node.val)
stack.append(node.left)
stack.append(node.right)
return FalseTwo Pointers - Fast & Slow (Cycle Detection)
4 practice problems
How to recall this pattern
Linked list + "cycle" or "middle" → use slow (1 step) and fast (2 steps). They meet inside a cycle. Reset one to head and walk both at 1 step to find the cycle start.Visual diagram
Theory
- Use two pointers moving at different speeds (slow = 1 step, fast = 2 steps).
- If there is a cycle, they will eventually meet inside the cycle.
- To find the cycle start: reset one pointer to head, then both move 1 step until they meet.
- Also used to find the middle of a linked list (when fast reaches the end, slow is at the middle).
Code template
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
def find_cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return NonePractice problems · 4
Slow moves 1 step, fast moves 2 steps. If there is a cycle, fast will eventually lap slow and they will meet. If fast reaches null, no cycle exists.
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseFirst detect cycle with fast/slow. Once they meet, reset slow to head. Now move both 1 step at a time — they meet at the cycle entry. This works because the distance from head to cycle start equals the distance from meeting point to cycle start.
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return NoneTreat the sequence of digit-square sums as a linked list. Use Floyd's cycle detection. If fast reaches 1 it is happy. If slow meets fast before that, there is a cycle and it is not happy.
def isHappy(n):
def next_num(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_num(n)
while fast != 1 and slow != fast:
slow = next_num(slow)
fast = next_num(next_num(fast))
return fast == 1Fast moves 2x the speed of slow. When fast reaches the end, slow is exactly at the middle. For even-length lists, this returns the second middle node.
def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowTwo Pointers - Fixed Separation (Nth Node from End)
3 practice problems
How to recall this pattern
"Nth from the end" → advance one pointer N steps ahead first, then walk both together. When the leader hits null, the follower is at the target.Visual diagram
Theory
- Advance the first pointer by N steps, then move both pointers together.
- When the first pointer hits the end, the second pointer is N nodes from the end.
- Use a dummy node before head to handle edge cases (e.g., removing the head node).
- Time: O(n) single pass, Space: O(1).
Code template
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
first = second = dummy
for _ in range(n + 1):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.nextPractice problems · 3
Use a dummy node. Advance first pointer n+1 steps. Then move both until first is null. Now second.next is the node to remove. Skip it by relinking.
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
first = second = dummy
for _ in range(n + 1):
first = first.next
while first:
first = first.next
second = second.next
second.next = second.next.next
return dummy.nextFind the length and make the list circular. The new head is at position (length - k). Walk to the node before the new head, break the circle there.
def rotateRight(head, k):
if not head or not head.next: return head
length = 1
tail = head
while tail.next:
tail = tail.next
length += 1
k %= length
if k == 0: return head
tail.next = head # make circular
curr = head
for _ in range(length - k - 1):
curr = curr.next
new_head = curr.next
curr.next = None
return new_headThree steps: (1) find the middle with slow/fast, (2) reverse the second half, (3) interleave the two halves by alternating links.
def reorderList(head):
# Find middle
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev, curr = None, slow.next
slow.next = None
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Merge two halves
first, second = head, prev
while second:
tmp1, tmp2 = first.next, second.next
first.next = second
second.next = tmp1
first, second = tmp1, tmp2Two Pointers - In-place Array Modification
5 practice problems
How to recall this pattern
"Remove/modify in-place with O(1) space" → use a slow (write) pointer and a fast (read) pointer. Fast scans everything; slow only advances when we keep an element.Visual diagram
Theory
- Use a slow pointer (write position) and a fast pointer (read position).
- Fast pointer scans every element; slow pointer only advances when we keep an element.
- Overwrites in-place without extra space. Common for removing duplicates or specific values.
- Time: O(n), Space: O(1). Order of remaining elements is preserved.
Code template
def remove_duplicates(nums):
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1Practice problems · 5
slow marks the last unique position. fast scans the array. When fast finds a new value, increment slow and copy it there. Array is sorted so duplicates are adjacent.
def removeDuplicates(nums):
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1slow is the write pointer. fast reads every element. If fast finds a non-val element, write it at slow and advance slow. Final slow value is the new length.
def removeElement(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slowSame as remove element but swap instead of overwrite. slow tracks the position for the next non-zero. Swap fast's non-zero with slow's zero, advance slow.
def moveZeroes(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1Allow at most 2 of each value. Write at slow only if slow < 2 (first two elements always valid) or the current value differs from nums[slow-2]. This generalizes to allow K duplicates.
def removeDuplicates(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slowDutch National Flag algorithm. Three pointers: lo (boundary for 0s), mid (scanner), hi (boundary for 2s). Swap 0s to the front and 2s to the back. mid only advances when it sees 0 or 1.
def sortColors(nums):
lo, mid, hi = 0, 0, len(nums) - 1
while mid <= hi:
if nums[mid] == 0:
nums[lo], nums[mid] = nums[mid], nums[lo]
lo += 1; mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[hi] = nums[hi], nums[mid]
hi -= 1Two Pointers - String Comparison with Backspaces
2 practice problems
How to recall this pattern
"Compare strings with backspaces (#) without building them" → process from the end, count backspaces, skip characters accordingly, then compare.Visual diagram
Theory
- Process strings from the end. When you hit a "#", count backspaces and skip characters.
- Compare characters only when both pointers are on non-skipped characters.
- Simulating from the end avoids building the final string, giving O(1) space.
- Time: O(n + m), Space: O(1).
Code template
def backspace_compare(s, t):
i, j = len(s) - 1, len(t) - 1
skip_s = skip_t = 0
while i >= 0 or j >= 0:
while i >= 0:
if s[i] == '#': skip_s += 1; i -= 1
elif skip_s > 0: skip_s -= 1; i -= 1
else: break
while j >= 0:
if t[j] == '#': skip_t += 1; j -= 1
elif skip_t > 0: skip_t -= 1; j -= 1
else: break
if i >= 0 and j >= 0 and s[i] != t[j]: return False
if (i >= 0) != (j >= 0): return False
i -= 1; j -= 1
return TruePractice problems · 2
Use a generator that walks the string from the end. On "#" increment skip counter. On a normal char with skip > 0, skip it. Otherwise yield it. Compare the two generated sequences.
def backspaceCompare(s, t):
def process(string):
i = len(string) - 1
skip = 0
while i >= 0:
if string[i] == '#': skip += 1; i -= 1
elif skip > 0: skip -= 1; i -= 1
else: yield string[i]; i -= 1
return list(process(s)) == list(process(t))Use a stack as the result. Push each character. If the top of the stack equals the current character, pop instead — this removes the adjacent pair. Final stack is the answer.
def removeDuplicates(s):
stack = []
for ch in s:
if stack and stack[-1] == ch:
stack.pop()
else:
stack.append(ch)
return ''.join(stack)Two Pointers - Expanding From Center (Palindromes)
2 practice problems
How to recall this pattern
"Find palindromic substrings" → for every index, expand outward with two pointers (left--, right++) while characters match. Check both odd-length (center = i) and even-length (center = i, i+1).Visual diagram
Theory
- For each index (and each pair of adjacent indices), expand outward while characters match.
- Handles both odd-length and even-length palindromes.
- Track the longest palindrome found so far by comparing lengths.
- Time: O(n²) worst case, Space: O(1). Can be improved to O(n) with Manacher's algorithm.
Code template
def longest_palindrome(s):
res = ""
for i in range(len(s)):
# Odd length
l, r = i, i
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res): res = s[l:r+1]
l -= 1; r += 1
# Even length
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res): res = s[l:r+1]
l -= 1; r += 1
return resPractice problems · 2
For each index, try expanding two palindromes: one centered at i (odd length) and one centered between i and i+1 (even length). Expand while characters match and track the longest found.
def longestPalindrome(s):
res = ""
for i in range(len(s)):
for l, r in [(i, i), (i, i+1)]:
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1; r += 1
return resSame expand-from-center approach, but instead of tracking the longest, increment a counter for every valid palindrome you encounter during expansion.
def countSubstrings(s):
count = 0
for i in range(len(s)):
for l, r in [(i, i), (i, i+1)]:
while l >= 0 and r < len(s) and s[l] == s[r]:
count += 1
l -= 1; r += 1
return countTwo Pointers - String Reversal
5 practice problems
How to recall this pattern
"Reverse something in-place" → left pointer at start, right pointer at end, swap and move inward until they meet.Visual diagram
Theory
- Place pointers at start and end of the string (or segment). Swap and move inward.
- For reversing words: reverse the whole string, then reverse each word individually.
- Works in-place with O(1) extra space on mutable arrays.
- Time: O(n), Space: O(1) if array is mutable.
Code template
def reverse_string(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1Practice problems · 5
Classic swap from both ends. left and right converge toward the middle, swapping characters at each step. Mutates the list in-place.
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1Two pointers from both ends. Skip non-vowels. When both land on vowels, swap them and move inward. Only vowels get reversed; all other characters stay in place.
def reverseVowels(s):
s = list(s)
vowels = set('aeiouAEIOU')
l, r = 0, len(s) - 1
while l < r:
while l < r and s[l] not in vowels: l += 1
while l < r and s[r] not in vowels: r -= 1
s[l], s[r] = s[r], s[l]
l += 1; r -= 1
return ''.join(s)split() handles multiple spaces and leading/trailing spaces by default. Reverse the resulting list of words and join with a single space.
def reverseWords(s):
return ' '.join(s.split()[::-1])Every 2k characters, reverse the first k. Python slice assignment makes this concise. Step through the string in chunks of 2k.
def reverseStr(s, k):
s = list(s)
for i in range(0, len(s), 2 * k):
s[i:i+k] = s[i:i+k][::-1]
return ''.join(s)Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase versions. If any mismatch, return False. If pointers meet, it is a palindrome.
def isPalindrome(s):
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum(): l += 1
while l < r and not s[r].isalnum(): r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1; r -= 1
return True