Two Pointers
Picture a sorted row of 1,000 people lined up by height, shortest to tallest. You need to find two people whose heights add up to exactly 300 cm. Put one finger on the shortest person and one on the tallest. Too small a total? Move the left finger one person to the right. Too big? Move the right finger one person to the left. You never check the same pair twice, so you cover the whole row in at most 1,000 steps: O(n), where a nested loop checking every pair would take close to 500,000 checks, O(n²). That is two pointers: the win is not a smarter data structure, it is a smarter scan order, using structure already in the input, usually that it is sorted. Interviewers use it to see whether you reach for hashing out of habit, or actually look at the shape of the problem first.
Two pointers vs hash maps
Both patterns often solve "find a pair or triple with some property," but they use different things about the input.
| Hash map | Two pointers | |
|---|---|---|
| Needs sorted input | No | Usually yes |
| Extra space | O(n) | O(1) |
| Keeps original indices | Yes | No, unless tracked separately |
| Typical time | O(n) | O(n), after an O(n log n) sort if needed |
Rule of thumb: if the array is already sorted, or you can sort it without needing the original order or indices, reach for two pointers to save space. If you need the original indices (like Two Sum) or the input cannot be reordered, use a hash map instead.
Two pointers works because in a sorted array, moving the left pointer right only increases the value there, and moving the right pointer left only decreases it. This one-directional behavior lets you throw away half the remaining search space at each step, instead of trying every pair.
For 3Sum-style problems: fix one element, then run two pointers on the remaining sorted subarray to find pairs that sum to the value you need. That is why sorting first turns an O(n³) triple-nested loop into O(n²).
Remember: hash map when you need original indices or the input can't be reordered. Two pointers when the input is sorted (or free to sort) and you can trade indices for O(1) space.
Moving elements in place
Picture tidying a shelf of 20 books where some titles repeat, without taking any books off the shelf or using a second shelf. One hand marks the next empty spot for a book you want to keep. The other hand scans ahead, looking for the next book worth keeping and sliding it back to that spot. Many two-pointer problems work exactly like this: removing duplicates, moving zeroes, partitioning, all using O(1) extra space, no second array. One pointer (write or slow) tracks where the next valid element should go. Another pointer (read or fast) scans ahead looking for valid elements to bring back.
def remove_duplicates(nums: list[int]) -> int:
"""Removes duplicates from a sorted array in place, returns new length."""
if not nums:
return 0
write = 1
for read in range(1, len(nums)):
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
return writeIn-place two-pointer solutions are easy to get subtly wrong around the boundary condition (!= vs <, starting write at 0 vs 1). Always trace through a small 2-3 element example by hand before calling it correct.
Remember: in a write/read pair,
writemarks where the next good value goes;readscans ahead to find it. Trace 2-3 elements by hand before you trust it.
Valid Palindrome
Valid Palindrome (LeetCode 125)
A palindrome reads the same forwards and backwards. Instead of building a cleaned string and reversing it, which costs extra space, walk from both ends toward the middle and compare characters directly.
Approach: Use left and right pointers starting at the two ends. Skip non-alphanumeric characters on either side. Compare lowercase versions of the characters; a mismatch means it is not a palindrome. Pointers crossing means success.
def is_palindrome(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 TrueComplexity: Time O(n), space O(1). No extra string built.
Common mistakes:
- Building a cleaned, lowercased copy of the string first. Correct, but O(n) extra space when O(1) is possible.
- Inner
whileloops missing theleft < rightbound, which causes an out-of-range index when the string is all punctuation. - Forgetting
.isalnum()covers both letters and digits, not just letters.
Remember: two pointers walking inward, skipping non-alphanumeric characters as they go, no extra string needed.
3Sum
Extending Two Sum's hash-map trick to three numbers gets messy fast because of duplicate handling. Sorting first and fixing one number turns this into a Two Sum variant you can solve with two pointers, and sorted order makes skipping duplicates mechanical.
Approach: Sort the array. For each index i (skipping duplicate values of nums[i]), run two pointers (left = i+1, right = n-1) across the rest of the array looking for pairs that sum to -nums[i]. Skip duplicate values at left and right after finding a match, so you do not record the same triplet twice.
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
if nums[i] > 0:
break # smallest remaining value is positive, no triplet can sum to 0
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return resultComplexity: Time O(n²): O(n log n) to sort plus an O(n) outer loop times an O(n) two-pointer scan. Space O(1) extra, not counting the sort and output.
Common mistakes:
- Forgetting to skip duplicate anchors, which produces duplicate triplets in the result.
- Skipping duplicates for
left/rightbefore recording the match instead of after. - Deduplicating the output with a hash set as a patch, instead of the sorted-skip technique. It works, but it is slower and messier.
Remember: sort first, fix one number, then two-pointer the rest. Skip duplicates right after recording a match, not before.
Container With Most Water
Container With Most Water (LeetCode 11)
Intuition: The area between two lines is min(height[left], height[right]) * (right - left). Starting pointers at both ends maximizes the width term first. The key insight: moving the pointer at the taller line inward can never increase the area, since the width shrinks and the height is still capped by the shorter line either way. So you always move the shorter line's pointer.
Approach: Start left = 0, right = n - 1. Track the max area seen. Move whichever pointer points to the shorter line inward. Repeat until the pointers meet.
def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
best = max(best, h * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1
return bestComplexity: Time O(n), a single pass with each pointer moving at most n times total. Space O(1).
Common mistakes:
- Trying every pair (O(n²)) instead of recognizing the "move the shorter side" argument.
- Moving the taller pointer, or moving both pointers every step. Both break the correctness proof.
- Forgetting the area formula uses
min, notmax, of the two heights, since water cannot rise above the shorter wall.
Remember: always move the pointer at the shorter line. Moving the taller one can only ever shrink the area.
A reusable linked list node
Linked list and tree problems reuse a minimal node class like this one. Get this boilerplate right once so it is not a distraction later.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return f"ListNode({self.val})"
def build_linked_list(values: list[int]) -> ListNode | None:
dummy = ListNode()
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.nextThe dummy head node is the trick worth remembering: it removes the special case of "is this the first node?" from insertion logic, since dummy.next always points at the real head.
Remember: a dummy head node turns "is this the first insert?" into a non-question.
dummy.nextis always the real head.