Two pointers

Two indices moving in controlled directions. It needs structure: sorted input, a palindrome, or a monotonic property.

Trigger in the prompt: 'Sorted array' plus 'a pair or a triple'; or a cycle in a linked structure.

easyLinked List Cycle

Detect whether a linked list contains a cycle.

Trigger

'Cycle', 'loop', with a constant-space requirement.

Approach
  1. A visited set works and is O(n) space. Say it, then improve.
  2. Floyd: slow moves one, fast moves two. If they meet, there is a cycle.
  3. The argument: inside the cycle the gap closes by one each step, so they must meet.
Target complexity

O(n) time, O(1) space.

Pitfall

Not checking `fast` and `fast.next` for null before advancing. It crashes on an acyclic list.

Say it out loud

“The set-based version is linear space; Floyd gets it in constant. The reason it works is that once both pointers are inside the cycle, the gap between them shrinks by one every step, so they're guaranteed to meet.”

Solve on LeetCode
easyValid Palindrome

Decide whether a string reads the same forwards and backwards, ignoring non-alphanumerics and case.

Trigger

'Palindrome' plus normalisation rules.

Approach
  1. Two pointers converging from both ends.
  2. Skip non-alphanumeric characters on each side before comparing.
  3. Ask about Unicode: case folding and accents are not the same as `lower()`.
Target complexity

O(n) time, O(1) space.

Pitfall

Building a cleaned copy of the string first. It works but costs O(n) space when O(1) was available.

Say it out loud

“Two pointers converging, skipping anything non-alphanumeric. Building a filtered copy first would be simpler but costs linear space. One clarifying question: is this ASCII? Unicode case folding isn't the same as lowercasing.”

Solve on LeetCode
easyValid Palindrome II

Decide whether a string can be made a palindrome by deleting at most one character.

Trigger

'Almost a palindrome', 'at most one deletion'.

Approach
  1. Two pointers as usual. On the first mismatch, branch.
  2. Two candidate strings: skip the left character, or skip the right one. Check both.
  3. One helper doing the plain palindrome check on a range keeps it clean.
Target complexity

O(n) time, O(1) space.

Pitfall

Trying to decide greedily which side to skip. You cannot — check both.

Say it out loud

“It's the standard two-pointer palindrome until the first mismatch, and at that point it branches: either the left character is the one to delete or the right one is. I can't decide greedily, so I check both, and each check is linear — the total is still linear because it only happens once.”

Solve on LeetCode
medium3Sum

Find all unique triples summing to zero.

Trigger

'Triples', 'sum to zero', 'no duplicate triples'.

Approach
  1. Sort first — that enables both the two-pointer inner loop and the deduplication.
  2. Fix the first element, then two pointers on the remainder.
  3. Deduplication is the real work: skip equal values at the fixed position, and skip equal values after finding a match.
  4. Early exit when the fixed element is positive.
Target complexity

O(n²) time, O(1) extra space beyond the sort.

Pitfall

Deduplicating with a set of tuples at the end. It works but is slower and misses the point of the sort.

Say it out loud

“Sorting does double duty: it enables the two-pointer inner loop and it makes deduplication a matter of skipping equal neighbours. That's what I'd be careful with — duplicate handling is where this problem is actually failed, not the algorithm.”

Solve on LeetCode
mediumContainer With Most Water

Find two lines forming the container holding the most water.

Trigger

'Maximum area between two lines'.

Approach
  1. Brute force is O(n²). Say it, then improve.
  2. Two pointers at the ends; always move the shorter one inward.
  3. Prove why that is safe: the area is limited by the shorter line, so keeping it and narrowing the width can only reduce the area — nothing is lost by discarding it.
Target complexity

O(n) time, O(1) space.

Pitfall

Moving the taller pointer, or moving both. Both break the correctness argument.

Say it out loud

“Two pointers from the ends, always moving the shorter line. The proof is that the area is capped by the shorter side, so any pair using it with a narrower width is strictly worse — which means discarding it loses nothing.”

Solve on LeetCode
mediumFind the Duplicate Number

Find the repeated value in an array of n+1 integers in the range 1..n, without modifying it.

Trigger

Read-only input, constant space, and a guaranteed duplicate — the disguised cycle problem.

Approach
  1. Say the reframe: treat the array as a function i → a[i]. A repeated value means two indices map to the same place, which is a cycle entry point.
  2. Floyd, phase one: find the meeting point inside the cycle.
  3. Phase two: reset one pointer to the start; advance both by one; they meet at the cycle entry, which is the duplicate.
  4. Mention binary search on the value range as the easier O(n log n) alternative.
Target complexity

O(n) time, O(1) space.

Pitfall

Sorting or using a set. Both are correct and both violate the stated constraints.

Say it out loud

“The constraints — read-only and constant space — rule out the obvious answers, which is the hint. If I treat the array as a function from index to value, a duplicate means two indices point to the same node, so the functional graph has a cycle and the duplicate is its entry point. That's Floyd, in two phases.”

Solve on LeetCode
mediumRemove Nth Node From End

Remove the n-th node counting from the end, in one pass.

Trigger

'From the end' plus 'one pass'.

Approach
  1. Two pointers with a gap of n: advance the fast one n steps, then move both.
  2. When fast hits the end, slow is just before the target.
  3. A sentinel head handles the case where the node to remove is the first one.
Target complexity

O(n) time, O(1) space, one pass.

Pitfall

Removing the head without a sentinel. It is the case everybody forgets.

Say it out loud

“Two pointers offset by n: when the leading one reaches the end, the trailing one is exactly at the predecessor of the target. I'll add a dummy head so removing the first node isn't a special case.”

Solve on LeetCode
mediumReorder List

Reorder a list as first, last, second, second-last, and so on.

Trigger

'Interleave the two halves', 'fold the list'.

Approach
  1. Three known sub-problems chained: find the middle, reverse the second half, interleave.
  2. Find the middle with fast and slow pointers.
  3. Say the decomposition out loud before coding — that is what makes this manageable.
Target complexity

O(n) time, O(1) space.

Pitfall

Not cutting the list at the middle before reversing, which leaves a cycle in the merged result.

Say it out loud

“This is three problems I already know, composed: find the middle with fast-slow, reverse the second half, then interleave. Saying the decomposition first makes the code straightforward. The one detail is severing the link at the midpoint before reversing, otherwise I create a cycle.”

Solve on LeetCode
mediumTwo Sum II

Find the two values summing to a target in a sorted array, returning their indices.

Trigger

'Sorted array' plus 'find a pair'.

Approach
  1. Because it is sorted, I do not need the hash map.
  2. Two pointers at both ends: if the sum is too small, move left up; too large, move right down.
  3. Justify why that is safe: moving the correct pointer can never skip the answer.
Target complexity

O(n) time, O(1) space.

Pitfall

Using the hash map anyway. It works but wastes the sorted property, which is the point of the problem.

Say it out loud

“The sorted order is the gift here — it means I can use two pointers instead of a hash map and get constant space. Each move is safe because if the sum is too small, no pair using the current left element can work.”

Solve on LeetCode
hardTrapping Rain Water

Compute how much water is trapped between bars of varying height.

Trigger

'Trapped water', 'held between the bars'.

Approach
  1. The key observation: water above position i is min(maxLeft, maxRight) − height[i].
  2. Version one: precompute both max arrays — O(n) time, O(n) space.
  3. Version two: two pointers, advancing whichever side has the smaller running max — O(1) space.
  4. Version three with a monotonic stack, filling layer by layer. Know at least two.
Target complexity

O(n) time, O(1) space with the two-pointer version.

Pitfall

Trying to compute it column by column with an inner scan — that is O(n²) and it is easy to slip into.

Say it out loud

“The insight is per-position: the water above a bar is the smaller of the two running maxima minus its own height. That gives an O(n)-space version immediately, and with two pointers advancing from the smaller side I can get it down to constant space.”

Solve on LeetCode