Two Pointers: Examples
Worked problems from the questions chapter, reasoning and code together, one shape at a time.
Converging
Two Sum II - Input Array Is Sorted gives a 1-indexed array, already sorted, and a target, and asks for the 1-indexed positions of the two numbers that add up to it. Exactly one solution exists.
This is the position-carries-information reasoning from Question 1, worked through to completion. Take numbers = [2, 7, 11, 15], target = 9. left starts at index 0 (2), right starts at index 3 (15).
Step one: 2 + 15 = 17, too big. Position already told us 15 is the largest value left in range, so pairing it with anything else in range can only be too big as well, right is the only side that could possibly fix this, move it back. right becomes index 2 (11).
Step two: 2 + 11 = 13, still too big, same reasoning, move right again. right becomes index 1 (7).
Step three: 2 + 7 = 9, matches the target exactly. left is at index 0, right is at index 1, and since the problem wants 1-indexed positions, the answer is [1, 2].
Notice what never happened, at no point did the algorithm check 2 against 11 and 2 against 7 separately as unrelated attempts. Each move eliminated an entire side, once 15 was ruled out, everything paired with 15 was ruled out with it, without checking any of those pairs directly.
// Two Sum II - Input Array Is Sorted
// https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
//
// Problem: given a 1-indexed array already sorted in ascending
// order, return the 1-indexed positions of the two numbers that add
// up to a given target. Exactly one solution exists.
//
// Sorted means position already tells us something about size, the
// rightmost value in range is always the largest remaining, the
// leftmost is always the smallest. That's enough to know, from one
// comparison, which side is safe to move, no lookup needed.
function twoSum(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) {
// Problem wants 1-indexed positions, not 0-indexed.
return [left + 1, right + 1];
}
if (sum < target) {
// Current sum is too small. left holds the smallest
// value remaining, so it's the only side that can ever
// be too small, moving it to a bigger value is safe.
left++;
} else {
// Current sum is too big. right holds the largest value
// remaining, so it's the only side that can ever be too
// big, moving it to a smaller value is safe.
right--;
}
}
return [];
}
module.exports = { twoSum };
3Sum gives an array and asks for every unique triplet that sums to 0, no duplicate triplets in the result. This is the case where the answer needs a third value outside the two moving pointers, noted at the end of Asking the Right Questions.
The array isn’t sorted to begin with, so sort it first, that’s what makes converging possible at all. Once sorted, fix one value as an anchor, sorted[i], and the rest of the problem becomes finding two numbers that sum to -sorted[i], which is exactly Two Sum II’s shape, just with a target computed from the anchor instead of given directly.
Take nums = [-1, 0, 1, 2, -1, -4], sorted to [-4, -1, -1, 0, 1, 2]. Anchor i = 1, value -1, target 1. left = 2 (-1), right = 5 (2), sum 1, a match, [-1, -1, 2]. Move both pointers, left = 3 (0), right = 4 (1), sum 1, another match, [-1, 0, 1]. Move again, left and right meet, this anchor is done.
Two duplicate-avoidance checks show up that Two Sum II never needed, since Two Sum II only ever wants one answer, not every unique one. First, skip an anchor equal to the previous anchor, sorted[2] = -1 is the same as sorted[1], using it again would just rediscover triplets already found with the first -1. Second, after a match, skip past any repeats of the values that just matched before continuing to converge, otherwise the same triplet gets recorded more than once from adjacent equal values.
// 3Sum
// https://leetcode.com/problems/3sum/description/
//
// Problem: given an array of integers, return all unique triplets
// that sum to 0. The result can't contain duplicate triplets.
//
// Sort first, then fix one value as an anchor and converge on the
// other two, same shape as Two Sum II, just with a moving target,
// -sorted[i] instead of a fixed one. The anchor is a third value
// held outside the two pointers, the triplet is anchor + left + right
// together, not something the two pointers produce on their own.
function threeSum(nums) {
const sorted = [...nums].sort((a, b) => a - b);
const result = [];
for (let i = 0; i < sorted.length - 2; i++) {
// Same anchor value as the previous iteration would only
// ever rediscover the same triplets, skip it.
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
let left = i + 1;
let right = sorted.length - 1;
const target = -sorted[i];
while (left < right) {
const sum = sorted[left] + sorted[right];
if (sum === target) {
result.push([sorted[i], sorted[left], sorted[right]]);
left++;
right--;
// Skip past any repeats of the values that just
// matched, so the same triplet isn't recorded twice.
while (left < right && sorted[left] === sorted[left - 1]) left++;
while (left < right && sorted[right] === sorted[right + 1]) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
module.exports = { threeSum };
Container With Most Water gives an array of heights, and any two indices form a container, holding water up to the shorter of the two heights, over a width equal to the distance between them. Return the largest amount of water any pair can hold. This is the case from Question 1 where the array isn’t sorted at all, order shows up purely in position, not value.
Every pair of indices forms a rectangle, and finding the one with the largest area is exactly what the problem is asking, checking all of them directly is the brute force, O(n^2).
Start at left = 0, right = n - 1, the widest rectangle possible, the maximum width available anywhere in the array. Every other pair has less width than this one, so the search begins at the one place width is already at its ceiling. From here, width can only go down, so the only lever left worth pulling is height.
Area is width times height, and the two pointers each contribute one of those. Width comes from position, right - left, known for free with no lookup. Height comes from the values, min(heights[left], heights[right]), the shorter of the two walls, since water can never sit higher than the shorter side without spilling over it.
Once height has that formula, the only question left is which direction to shrink the width from, left++ or right--. The side holding the smaller height moves. min(heights[left], heights[right]) only ever depends on whichever wall is shorter, the taller wall isn’t the bottleneck at all, it could be far taller and the height would still be capped by the shorter one. So keeping the shorter wall in place and giving up width by moving the taller one buys nothing, the cap stays exactly where it was, while width, the one thing guaranteed to only shrink, has already gotten worse. Moving the shorter wall is the only move with any chance of raising the cap for the next rectangle, which is the entire safety argument this pattern needs.
Take heights = [1, 8, 6, 2, 5, 4, 8, 3, 7].
left right heights[left] heights[right] width area move
0 8 1 7 8 8 left (shorter)
1 8 8 7 7 49 right (shorter)
1 7 8 3 6 18 right (shorter)
1 6 8 8 5 40 right (tie, either side)
1 5 8 4 4 16 right (shorter)
1 4 8 5 3 15 right (shorter)
1 3 8 2 2 4 right (shorter)
1 2 8 6 1 6 right (shorter)
left moves exactly once, at the very first step, since after that heights[1] = 8 stays the taller side for the rest of the run, and right is always the one being abandoned. The largest area found along the way is 49, at the second step, and nothing after it beats that, so 49 is the answer.
// Container With Most Water
// https://leetcode.com/problems/container-with-most-water/description/
//
// Problem: given an array of heights, each pair of indices forms a
// container with the x-axis, holding water up to the shorter of the
// two heights, over a width equal to the distance between them.
// Return the maximum amount of water any pair can hold.
//
// This array isn't sorted, there's no numeric order to exploit. The
// order being exploited here is positional: width is always
// right - left, known for free from position, no lookup needed. The
// safety argument comes from the values, whichever side is shorter
// caps the area no matter what the other side is, so moving that
// side is the only move that could ever find something better.
function maxArea(heights) {
let left = 0;
let right = heights.length - 1;
let best = 0;
while (left < right) {
const width = right - left;
const area = Math.min(heights[left], heights[right]) * width;
best = Math.max(best, area);
// The shorter wall is the one capping the area. Keeping it
// and shrinking the width can never beat what we already
// have, so it's the only side worth abandoning.
if (heights[left] < heights[right]) {
left++;
} else {
right--;
}
}
return best;
}
module.exports = { maxArea };
Valid Palindrome gives a string and asks whether it reads the same forwards and backwards, counting only letters and digits, ignoring case, ignoring everything else. This is the case from Question 1 with no numeric order at all, just a fixed first character and a fixed last character to converge between.
Punctuation and spaces get skipped entirely before any comparison happens, "A man, a plan, a canal: Panama" really means comparing just "amanaplanacanalpanama", letters only, lowercased.
Take "race a car", which strips down to "raceacar". left = 0 (r), right = 7 (r), match, both move inward. left = 1 (a), right = 6 (a), match, both move inward. left = 2 (c), right = 5 (c), match, both move inward. left = 3 (e), right = 4 (a), mismatch, stop immediately, the answer is false.
That last step is the whole safety argument. The moment a mismatch shows up, nothing else in the string needs checking, one failed comparison already proves the string isn’t a palindrome. And every match settles that pair permanently, a matched r at the two ends is never revisited once both pointers have moved past it, there’s no scenario where re-checking it later would change anything.
// Valid Palindrome
// https://leetcode.com/problems/valid-palindrome/description/
//
// Problem: given a string, considering only letters and digits and
// ignoring case, determine whether it reads the same forwards and
// backwards.
//
// No numeric order here at all, just positional order, a fixed
// first character and last character. Converging inward compares
// character by character. A mismatch proves the answer is false
// immediately, no need to check anything else. A match settles that
// pair for good, both sides move inward without ever revisiting it.
function isAlphanumeric(ch) {
return /[a-z0-9]/i.test(ch);
}
function isPalindrome(s) {
let left = 0;
let right = s.length - 1;
while (left < right) {
// Skip anything that isn't a letter or digit before comparing.
while (left < right && !isAlphanumeric(s[left])) left++;
while (left < right && !isAlphanumeric(s[right])) right--;
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left++;
right--;
}
return true;
}
module.exports = { isPalindrome };
Trapping Rain Water gives an array of wall heights and asks for the total water trapped after it rains. This is the case from Question 5 with a small running value carried alongside the pointers, maxLeft and maxRight.
Water trapped at any single position is min(maxLeftOf(i), maxRightOf(i)) - height[i], the shorter of the two boundary walls decides how high the water can sit there, same idea as Container With Most Water, just asked at every position instead of between two chosen walls once.
Getting to the two-pointer version. Start from the direct approach: build a leftMax array, left to right, and a rightMax array, right to left, then read both at every index. leftMax[i] only ever depends on indices before it, so building it left to right means each value is only ever needed once, right when it’s produced, nothing past that point needs to look back. Storing the full array is wasted effort, a single running variable, the max so far, carries everything actually needed. The same is true of rightMax, walking right to left.
That’s the whole optimization, except for one snag: the two running variables come from walks in opposite directions, and we need both at the same index at once. Two pointers is what resolves that, left carrying its running max forward, right carrying its running max backward, both walks happening at the same time, converging toward the middle. At any moment, one side is fully settled and the other isn’t yet, so the real question becomes deciding which side to resolve next, and that’s what heights[left] versus heights[right] answers, cheaply, without waiting for either walk to finish.
Why the comparison is safe. Say heights[left] < maxLeft, so left is not itself a new high point. Split on heights[left] against heights[right]. right sits somewhere within [left, end], so heights[right] alone proves the true max from left to the end is at least heights[right]. When heights[right] > heights[left], that’s already bigger than heights[left], and combined with maxLeft being tracked exactly, maxLeft is what decides the water level here, right’s side is provably not the bottleneck.
If instead heights[left] >= maxLeft, there’s nothing to prove at all, this position is the tallest thing seen so far on this side, it can’t trap water regardless of what’s on the other side, maxLeft just updates to heights[left] and the answer here is 0.
I’ll be honest about the piece I’m not fully deriving here, showing that maxLeft is always safe to use rather than the true (unknown) max from the right relies on a subtler invariant than a single comparison, it holds, this is a standard, thoroughly checked algorithm, but a tight proof of it takes more space than fits cleanly here.
Take heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].
left right h[left] h[right] maxLeft maxRight move water added total
0 11 0 1 0 0 left 0 0
1 11 1 1 1 0 right 0 0
1 10 1 2 1 1 left 0 0
2 10 0 2 1 1 left 1 1
3 10 2 2 2 1 right 0 1
3 9 2 1 2 2 right 1 2
3 8 2 2 2 2 right 0 2
3 7 2 3 2 2 left 0 2
4 7 1 3 2 2 left 1 3
5 7 0 3 2 2 left 2 5
6 7 1 3 2 2 left 1 6
left and right meet at index 7, loop ends, total water trapped is 6, which matches the known answer for this input.
// Trapping Rain Water
// https://leetcode.com/problems/trapping-rain-water/description/
//
// Problem: given an array of wall heights, return the total amount
// of water trapped between the walls after it rains.
//
// Water trapped at any index i is min(maxLeftOf(i), maxRightOf(i))
// minus height[i], the shorter of the two boundary walls decides
// the water level, same idea as Container With Most Water, just
// asked at every index instead of once between two chosen walls.
//
// Alongside left and right, track a running maxLeft and maxRight,
// the tallest wall seen so far from each side. Those only ever grow
// and never need correcting, which is what keeps this within the
// two-pointer pattern rather than needing two full extra passes.
function trap(heights) {
let left = 0;
let right = heights.length - 1;
let maxLeft = 0;
let maxRight = 0;
let water = 0;
while (left < right) {
if (heights[left] < heights[right]) {
// heights[right] is somewhere to the right of left, so
// it's proof on its own that maxRightOf(left) is at
// least heights[right], which is already more than
// heights[left]. maxLeft is known exactly, so it alone
// decides the water level here, no need to know the
// real maxRightOf(left).
if (heights[left] >= maxLeft) {
maxLeft = heights[left];
} else {
water += maxLeft - heights[left];
}
left++;
} else {
// Same argument mirrored, heights[left] proves
// maxLeftOf(right) is at least heights[left], already
// more than heights[right], so maxRight alone decides.
if (heights[right] >= maxRight) {
maxRight = heights[right];
} else {
water += maxRight - heights[right];
}
right--;
}
}
return water;
}
module.exports = { trap };
Squares of a Sorted Array gives an array sorted in ascending order, possibly containing negatives, and asks for the squares of every element, sorted in ascending order. No target to match here, which makes it a different shape from every Converging problem so far.
Squaring a negative number can flip its rank entirely, -10 is the smallest value in the input but 100 is the largest square. Sorting the squares directly would mean starting over, ignoring the order the input already has, and paying O(n log n) for it.
The input’s order isn’t wasted though. In a sorted array, the most negative value sits at the far left and the most positive at the far right, and the largest absolute value, the one that produces the largest square, has to be one of those two, nothing in the middle can beat both ends at once. So at every step, comparing nums[left] and nums[right] by their squares tells us which one is currently the largest square remaining, no scan needed.
That flips the usual direction of filling an array. The largest square is known first, but it belongs at the last position of the sorted result, not the first. So the result array gets filled back to front, largest square placed at the highest open slot, and whichever pointer produced it moves inward for the next comparison.
Take nums = [-4, -1, 0, 3, 10].
left right nums[left] nums[right] left² right² placed at value move
0 4 -4 10 16 100 4 100 right
0 3 -4 3 16 9 3 16 left
1 3 -1 3 1 9 2 9 right
1 2 -1 0 1 0 1 1 left
2 2 0 0 0 0 0 0 either
Reading the value column bottom to top gives the result, [0, 1, 9, 16, 100], already in sorted order, without ever sorting the squares directly.
// Squares of a Sorted Array
// https://leetcode.com/problems/squares-of-a-sorted-array/description/
//
// Problem: given an array sorted in ascending order, possibly with
// negative numbers, return the squares of every element, sorted in
// ascending order.
//
// No target here, just a comparison at each step. In a sorted array,
// the largest absolute value always sits at one of the two ends,
// the most negative number on the left or the most positive on the
// right, so the largest square is always at one of the two ends too.
// Fill the result from the back, largest first, and move whichever
// pointer produced it.
function sortedSquares(nums) {
const n = nums.length;
const result = new Array(n);
let left = 0;
let right = n - 1;
let i = n - 1;
while (left <= right) {
const leftSquare = nums[left] * nums[left];
const rightSquare = nums[right] * nums[right];
if (leftSquare > rightSquare) {
result[i] = leftSquare;
left++;
} else {
result[i] = rightSquare;
right--;
}
i--;
}
return result;
}
module.exports = { sortedSquares };
Boats to Save People gives each person’s weight and a weight limit, a boat carries at most two people, and asks for the minimum number of boats to carry everyone. Every problem so far in this bucket asked “find” or “compute” something, this one asks for the smallest count, a different objective entirely.
Sort first. The heaviest person remaining always needs a boat, no way around that, so the only real question at each step is whether the lightest person remaining can ride along with them. That’s the whole decision the two pointers are making, over and over.
Two things make that decision safe. If the lightest remaining person can’t fit with the heaviest, nobody else remaining can either, everyone else is at least as heavy as the lightest, so the heaviest goes alone, no point checking anyone in between. If the lightest can fit, pairing them here is never worse than saving the lightest for someone else, since every other remaining person is heavier and has an easier time fitting with somebody regardless of who takes the lightest spot.
The code ends up looking close to Two Sum, sorted array, left and right converging, comparing a sum against a threshold, same skeleton. What’s different is what happens after the comparison. Two Sum stops the moment it finds a match, the comparison’s whole job is to locate one pair and return. Here there’s no “found it” to stop on, every single step produces a boat regardless of the outcome, boats++ runs unconditionally each iteration. The comparison isn’t deciding when to stop, it’s deciding how much progress this one boat buys, two people or one, right always moves, left only moves when the pair actually fits.
Take people = [3, 2, 2, 1], limit = 3, sorted to [1, 2, 2, 3].
left right sorted[left] sorted[right] sum fits? boats
0 3 1 3 4 no 1 (right alone)
0 2 1 2 3 yes 2 (paired)
1 1 2 2 4 no 3 (right alone)
Three boats, matching the known answer for this input.
// Boats to Save People
// https://leetcode.com/problems/boats-to-save-people/description/
//
// Problem: given each person's weight and a weight limit per boat,
// where a boat carries at most two people, return the minimum
// number of boats needed to carry everyone. Every person fits alone
// under the limit on their own.
//
// Sort first, then converge. The heaviest person remaining always
// needs a boat, the only question is whether the lightest person
// remaining can share it with them. If the lightest can't fit with
// the heaviest, nobody heavier could have either, so the heaviest
// goes alone. If the lightest can fit, pairing them is always at
// least as good as pairing the lightest with anyone else, since
// everyone else has an easier time fitting with someone regardless.
function numRescueBoats(people, limit) {
const sorted = [...people].sort((a, b) => a - b);
let left = 0;
let right = sorted.length - 1;
let boats = 0;
while (left <= right) {
if (sorted[left] + sorted[right] <= limit) {
// Lightest remaining person fits with the heaviest.
left++;
}
// Heaviest remaining person always takes a boat, either
// alone or paired with the lightest, one boat either way.
right--;
boats++;
}
return boats;
}
module.exports = { numRescueBoats };
Fast and Slow
Remove Duplicates from Sorted Array gives a sorted array and asks to remove duplicates in place, keeping one copy of each value, relative order preserved, and return the new length. The kept values have to end up in the first part of the array itself, no separate output array allowed.
Without sorting, “have I already kept this value” would need a set, remembering every value written so far, O(n) extra space, which the problem explicitly rules out. Sorted order removes that need entirely, duplicates are guaranteed to sit next to each other, so a new value only ever needs comparing against the single most recently kept value, not against everything kept so far.
slow marks the last position of the cleaned-up region, fast scans ahead one element at a time. Whenever nums[fast] differs from nums[slow], it’s a new value worth keeping, slow advances and nums[fast] gets written there. Whenever it matches, fast just moves on, nothing gets written, that duplicate is discarded.
Take nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4].
fast nums[fast] nums[slow] action
1 0 0 skip (duplicate)
2 1 0 keep, slow = 1, nums[1] = 1
3 1 1 skip (duplicate)
4 1 1 skip (duplicate)
5 2 1 keep, slow = 2, nums[2] = 2
6 2 2 skip (duplicate)
7 3 2 keep, slow = 3, nums[3] = 3
8 3 3 skip (duplicate)
9 4 3 keep, slow = 4, nums[4] = 4
slow ends at 4, so the new length is 5, and the first five positions hold [0, 1, 2, 3, 4], matching the known result for this input.
// Remove Duplicates from Sorted Array
// https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/
//
// Problem: given a sorted array, remove duplicates in place so each
// unique value appears once, keeping relative order, and return the
// new length. The first part of the array, up to that length, must
// hold the result.
//
// Without sorting, checking "have I kept this value already" would
// need a set, remembering everything written so far, O(n) extra
// space. Sorted means duplicates are guaranteed to sit next to each
// other, so the only check needed is against the single most
// recently kept value, no set required.
function removeDuplicates(nums) {
let slow = 0;
for (let fast = 1; fast < nums.length; fast++) {
// A new value only ever needs comparing against the last
// one kept, sorted order guarantees nothing else could
// possibly match it.
if (nums[fast] !== nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
module.exports = { removeDuplicates };
Move Zeroes gives an array and asks to move every zero to the end, keeping the relative order of the non-zero elements, in place, no copy of the array allowed. Unlike Remove Duplicates, this array isn’t sorted at all, only the original relative order needs preserving, the weaker version of order from Question 1.
The decision at each step is simpler than Remove Duplicates too, no comparison against slow’s value needed, just whether nums[fast] is zero or not. But there’s a wrinkle Remove Duplicates didn’t have, a discarded duplicate can just be overwritten and forgotten, a zero can’t, it still has to exist somewhere in the final array, just pushed to the end. That’s why slow and fast swap places here instead of one overwriting the other, swapping relocates whatever was sitting at slow (a zero, or something already correctly placed) into fast’s old spot rather than losing it.
Take nums = [0, 1, 0, 3, 12].
fast nums[fast] action array after
0 0 skip (zero) [0, 1, 0, 3, 12]
1 1 swap(slow=0, fast=1), slow=1 [1, 0, 0, 3, 12]
2 0 skip (zero) [1, 0, 0, 3, 12]
3 3 swap(slow=1, fast=3), slow=2 [1, 3, 0, 0, 12]
4 12 swap(slow=2, fast=4), slow=3 [1, 3, 12, 0, 0]
Final array is [1, 3, 12, 0, 0], non-zero elements in their original relative order, every zero pushed to the end.
// Move Zeroes
// https://leetcode.com/problems/move-zeroes/description/
//
// Problem: given an array, move all zeroes to the end while keeping
// the relative order of the non-zero elements, in place, without
// making a copy of the array.
//
// Unlike Remove Duplicates, the decision here doesn't need to
// compare fast against slow at all, only whether nums[fast] is
// zero. And since the zeroes can't just be discarded, they still
// need to exist somewhere in the array, slow and fast swap places
// instead of overwriting, which relocates a zero into fast's old
// spot rather than losing track of it.
function moveZeroes(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
}
module.exports = { moveZeroes };
Remove Duplicates from Sorted Array II is the same problem as before, but each value is now allowed to appear up to twice, not just once. Comparing nums[fast] against nums[slow], the single most recently kept value, isn’t enough anymore, that rule only ever lets one copy through.
The fix moves the comparison back one more slot. Instead of checking against the last kept value, check against the value kept two positions before slow. If nums[fast] matches that, keeping it would make three copies of the same value in a row, since the two positions right before it already hold that value, so it gets skipped. If it doesn’t match, keeping it is safe, either it’s a genuinely new value, or it’s a duplicate but fewer than two copies have been kept so far.
Take nums = [1, 1, 1, 2, 2, 3].
fast nums[fast] slow check action
0 1 0 slow < 2 keep, slow = 1
1 1 1 slow < 2 keep, slow = 2
2 1 2 1 == nums[0] (1) skip (third copy)
3 2 2 2 != nums[0] (1) keep, slow = 3
4 2 3 2 != nums[1] (1) keep, slow = 4
5 3 4 3 != nums[2] (2) keep, slow = 5
slow ends at 5, the new length, and the first five positions hold [1, 1, 2, 2, 3], matching the expected result, two copies of 1, two copies of 2, one 3.
// Remove Duplicates from Sorted Array II
// https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/description/
//
// Problem: given a sorted array, remove duplicates in place so each
// value appears at most twice, keeping relative order, and return
// the new length.
//
// Same shape as Remove Duplicates from Sorted Array, but comparing
// against the single last kept value isn't enough anymore, that
// would only ever allow one copy through. The comparison moves back
// one more slot, against the value kept two positions before slow,
// since that's exactly what tells us whether keeping the current
// value would be a third copy in a row.
function removeDuplicates(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
// The first two positions are always safe to keep, there's
// no way to have three copies yet. Past that, only keep a
// value if it differs from what's two slots back in the
// write region, matching there would make this a third copy.
if (slow < 2 || nums[fast] !== nums[slow - 2]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
module.exports = { removeDuplicates };
Sort Colors, the Dutch National Flag problem, gives an array containing only 0s, 1s, and 2s and asks to sort it in place, in one pass, without counting occurrences first. Move Zeroes got away with two pointers because it only had two categories, zero and non-zero. Three categories need a third pointer, since a two-way split can only ever describe a boundary between two regions, not three.
low marks the edge of the confirmed-0 region, everything before it is settled. high marks the edge of the confirmed-2 region, everything after it is settled. mid scans forward, classifying whatever it currently sits on and deciding what to do with it.
If nums[mid] is 0, swap it with nums[low], extending the confirmed-0 region, and both low and mid advance, the value that came back from low is always safe to skip past, since the region before mid was already fully classified earlier, it could only have held a 0 or a 1, never an unclassified value. If nums[mid] is 1, it’s already in the right place, mid just advances. If nums[mid] is 2, swap it with nums[high], extending the confirmed-2 region, but mid does not advance here, whatever just got swapped in from high hasn’t been looked at yet, and skipping it could leave it misclassified.
Take nums = [2, 0, 2, 1, 1, 0].
mid nums[mid] low high action array after
0 2 0 5 swap(mid, high), high = 4 [0, 0, 2, 1, 1, 2]
0 0 0 4 swap(low, mid), low=1, mid=1 [0, 0, 2, 1, 1, 2]
1 0 1 4 swap(low, mid), low=2, mid=2 [0, 0, 2, 1, 1, 2]
2 2 2 4 swap(mid, high), high = 3 [0, 0, 1, 1, 2, 2]
2 1 2 3 mid = 3 [0, 0, 1, 1, 2, 2]
3 1 2 3 mid = 4 [0, 0, 1, 1, 2, 2]
mid passes high, loop ends, final array [0, 0, 1, 1, 2, 2], fully sorted in one pass.
// Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// Problem: given an array containing only 0s, 1s, and 2s, sort it
// in place, in one pass, without counting occurrences first.
//
// Move Zeroes only needed two pointers because it only had two
// categories, zero and non-zero. Three categories need a third
// pointer, low marks the boundary of the confirmed-0 region, high
// marks the boundary of the confirmed-2 region, mid scans forward
// classifying whatever it currently sits on.
function sortColors(nums) {
let low = 0;
let mid = 0;
let high = nums.length - 1;
while (mid <= high) {
if (nums[mid] === 0) {
[nums[low], nums[mid]] = [nums[mid], nums[low]];
low++;
mid++;
} else if (nums[mid] === 1) {
mid++;
} else {
[nums[mid], nums[high]] = [nums[high], nums[mid]];
high--;
// mid does not advance here. The value just swapped in
// from high hasn't been classified yet, it needs to be
// checked on the next iteration, not skipped past.
}
}
}
module.exports = { sortColors };
Linked List
Linked List Cycle gives the head of a linked list and asks whether it contains a cycle, some node’s next eventually leads back to a node already visited instead of ending at null. No random access here, no indices, only .next, which is why this bucket works mechanically differently from the other two.
The direct fix is a set, record every node visited, check each new node against it, seen-before from hashing applied here. That works, but it costs O(n) space, one entry per node. Two pointers gets the same answer in O(1) space by moving at different speeds instead of remembering anything.
slow moves one node per step, fast moves two. If there’s no cycle, fast simply reaches the end first, nothing more to check. If there is a cycle, fast enters it before slow does, and every step afterward closes the gap between them by exactly one node, since fast gains one extra step of ground per iteration. A shrinking gap that never resets means they’re guaranteed to land on the same node eventually, not just pass each other, which is what makes slow === fast a reliable signal.
Take a list A(3) -> B(2) -> C(0) -> D(-4), where D.next points back to B instead of null.
step slow fast meet?
0 A A no (start)
1 B C no
2 C B no
3 D D yes
fast computed as two .next hops each step, A -> B -> C on step 1, C -> D -> B on step 2 (following the cycle back), B -> C -> D on step 3, where it lands on D at the same time slow does. They meet, a cycle exists.
// Linked List Cycle
// https://leetcode.com/problems/linked-list-cycle/description/
//
// Problem: given the head of a linked list, determine whether it
// contains a cycle, some node's `next` eventually points back to a
// node already visited, rather than ending at null.
//
// A set of visited nodes would answer this in O(n) space, checking
// each node against everything seen so far, the seen-before pattern
// from hashing. Two pointers at different speeds answers it in O(1)
// space instead. If there's no cycle, the faster pointer simply
// reaches the end first. If there is one, the faster pointer enters
// the cycle first and laps the slower one, since it closes the gap
// between them by one node every step, guaranteeing they land on
// the same node eventually rather than passing each other.
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) return true;
}
return false;
}
module.exports = { hasCycle };
Linked List Cycle II asks a harder question than the last one, not just whether a cycle exists, but where it starts. Same O(1) space constraint, no set of visited nodes, no modifying the list.
Phase one is identical to before, slow and fast at different speeds until they meet somewhere inside the cycle. The new part is phase two, and the reasoning behind it is worth working through rather than taking on faith.
Let a be the distance from head to the cycle’s start, b the distance from the start to wherever slow and fast meet, and c the rest of the way around the cycle back to the start, so the cycle’s total length is b + c. When they meet, slow has traveled a + b. fast moves twice as fast in the same time, so it’s traveled 2(a + b). fast’s extra distance beyond slow’s is entirely laps around the cycle, some whole number of them, call it k, so 2(a + b) - (a + b) = kL, which simplifies to a + b = kL. Substituting L = b + c and solving for a gives a = c + (k - 1)L.
That equation says a and c are the same distance, plus possibly a few extra full laps around the cycle. Extra full laps don’t matter, walking an exact multiple of the cycle’s length just returns to the same node. So starting one pointer at head and another at the meeting point, and moving both one step at a time, they’re guaranteed to land on the same node after a steps, which is exactly the cycle’s start.
Take the same list as before, A(3) -> B(2) -> C(0) -> D(-4), D.next pointing back to B. Phase one found slow and fast meeting at D. For phase two, ptr1 resets to A, ptr2 stays at D.
step ptr1 ptr2 meet?
0 A D no
1 B B yes
Both land on B after one step, which is the actual start of the cycle in this list, a = 1 (A to B), c = 1 (D to B), matching the derivation exactly.
// Linked List Cycle II
// https://leetcode.com/problems/linked-list-cycle-ii/description/
//
// Problem: given the head of a linked list, if it has a cycle,
// return the node where the cycle begins. If it doesn't, return
// null. Same O(1) space constraint as Linked List Cycle, no
// modifying the list, no extra structure to track visited nodes.
//
// Phase one is identical to Linked List Cycle, slow and fast moving
// at different speeds until they meet somewhere inside the cycle.
// Phase two uses that meeting point, reset one pointer to head,
// leave the other at the meeting point, advance both one step at a
// time, they're guaranteed to meet again exactly at the cycle's
// start.
//
// Why that works: let a = distance from head to the cycle's start,
// b = distance from the cycle's start to the meeting point, c = the
// rest of the cycle back to the start, so the cycle length is b + c.
// When slow and fast meet, slow has traveled a + b, fast has
// traveled twice that, and fast's extra distance beyond slow's is
// some whole number of full laps around the cycle. Working through
// that equality gives a = c, plus possibly a few extra full laps,
// which don't matter, a full lap returns to the same node. So
// walking `a` steps from head and `c` steps from the meeting point
// land on the same node, the cycle's start.
function detectCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let ptr = head;
while (ptr !== slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
module.exports = { detectCycle };
Middle of the Linked List gives the head of a linked list and asks for the middle node, the second of the two middle nodes if the list has an even length. A linked list has no O(1) length the way an array does, so the direct fix is two passes, one to count the nodes, one to walk to the halfway point.
fast covers twice the ground slow does in the same number of steps, so by the time fast has walked the whole list, slow has walked exactly half of it, one pass instead of two.
Odd length, 1 -> 2 -> 3 -> 4 -> 5.
step slow fast
0 1 1
1 2 3
2 3 5
fast reaches 5, fast.next is null, loop stops, slow is at 3, the exact middle.
Even length, 1 -> 2 -> 3 -> 4.
step slow fast
0 1 1
1 2 3
2 3 null
fast becomes null after the second step (3.next.next runs past the end), loop stops, slow is at 3, the second of the two middle nodes, matching what the problem asks for.
// Middle of the Linked List
// https://leetcode.com/problems/middle-of-the-linked-list/description/
//
// Problem: given the head of a linked list, return its middle node.
// If there are two middle nodes (an even length list), return the
// second one.
//
// A linked list has no O(1) length the way an array does, so the
// direct fix is two passes, walk once to count the nodes, then walk
// again to the halfway point. Fast and slow gets it in one pass
// instead. fast covers twice the ground of slow in the same number
// of steps, so by the time fast has reached the end, slow has
// covered exactly half the distance.
function middleNode(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
module.exports = { middleNode };
Reorder List asks to rearrange L0 -> L1 -> ... -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ..., alternating from the front and the back, in place. A linked list can only be walked forward, so reaching “the back” repeatedly would normally mean re-walking from the head every time, or paying for an array of node references to get O(1) access from either end. Three phases, each one already covered elsewhere in this chapter, avoid both.
Take 1 -> 2 -> 3 -> 4 -> 5.
Phase 1, find the middle. Exactly Middle of the Linked List, fast and slow. slow ends at 3.
Phase 2, cut and reverse the second half. slow.next gives the second half, 4 -> 5, and slow.next = null cuts it away from the first half, 1 -> 2 -> 3. Reversing 4 -> 5 in place, standard pointer reversal, gives 5 -> 4. Reversing it is what turns “the back of the list” into something walkable front-to-back, 5 is now first, 4 is now second, in the exact order they need to be read off during the merge.
Phase 3, merge by alternating. Walk both halves at once, first through 1 -> 2 -> 3, second through 5 -> 4, splicing one node from each into the result before moving both forward.
first second splice result so far
1 5 1.next=5, 5.next=2 1 -> 5 -> 2 -> 3
2 4 2.next=4, 4.next=3 1 -> 5 -> 2 -> 4 -> 3
3 null loop ends (second empty) 1 -> 5 -> 2 -> 4 -> 3
Final list, 1 -> 5 -> 2 -> 4 -> 3, matching L0 -> Ln -> L1 -> Ln-1 -> L2 exactly, with the middle node, 3, left on its own at the end since the list has an odd length.
// Reorder List
// https://leetcode.com/problems/reorder-list/description/
//
// Problem: given a list L0 -> L1 -> ... -> Ln, reorder it in place
// to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ..., without a second
// data structure to index nodes from both ends at once.
//
// Three phases, each one already covered elsewhere in this chapter.
// Find the middle with fast and slow, exactly like Middle of the
// Linked List. Reverse everything after the middle, so the second
// half can now be walked front-to-back instead of needing to be
// walked backward. Then merge the two halves by alternating nodes,
// one from the front half, one from the reversed back half.
function reorderList(head) {
if (!head || !head.next) return;
// Phase 1: find the middle.
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
// Phase 2: cut the list in half and reverse the second half.
let second = slow.next;
slow.next = null;
let prev = null;
while (second) {
const next = second.next;
second.next = prev;
prev = second;
second = next;
}
second = prev;
// Phase 3: merge by alternating nodes from each half.
let first = head;
while (second) {
const firstNext = first.next;
const secondNext = second.next;
first.next = second;
second.next = firstNext;
first = firstNext;
second = secondNext;
}
}
module.exports = { reorderList };
Swapping Nodes in a Linked List gives a list and an integer k, and asks to swap the values of the kth node from the start and the kth node from the end. The start side is easy, walk k - 1 steps from head. The end side is the actual problem, a linked list has no length to compute an index from, unlike an array where “kth from the end” is just length - k.
The fix doesn’t compute an index at all, it keeps a fixed gap between two pointers instead. Once one pointer is k - 1 steps ahead of the other, sliding both forward together, one step each, keeps that same gap the whole way. The moment the front pointer reaches the last node, the back pointer has to be exactly k nodes from the end, since the gap between them never changed, only where in the list it’s sitting.
Take head = [1, 2, 3, 4, 5], k = 2.
first walks 1 step from head, landing on node 2 (the 2nd from the start). second starts back at head, runner starts at first’s position, and both slide forward together until runner runs out of next.
step runner second
0 2 1
1 3 2
2 4 3
3 5 4
runner reaches 5, the last node, runner.next is null, loop stops. second is at node 4, the 2nd from the end. Swap the values at first (2) and second (4), giving [1, 4, 3, 2, 5].
// Swapping Nodes in a Linked List
// https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/
//
// Problem: given the head of a linked list and an integer k, swap
// the values of the kth node from the start and the kth node from
// the end (1-indexed), then return the list.
//
// The kth node from the start is easy, walk k - 1 steps from head.
// The kth node from the end is the problem, a linked list has no
// length to compute an index from directly. The fix is a fixed gap
// between two pointers instead of a computed index: once one
// pointer is k - 1 steps ahead of the other, sliding both forward
// together until the front one hits the last node leaves the back
// one exactly k nodes from the end, the gap between them never
// changes, only where it sits in the list does.
function swapNodes(head, k) {
let first = head;
for (let i = 1; i < k; i++) {
first = first.next;
}
// first is now the kth node from the start.
let second = head;
let runner = first;
while (runner.next) {
runner = runner.next;
second = second.next;
}
// runner reached the last node, second is now the kth from the
// end, having moved the exact same number of steps as runner.
[first.val, second.val] = [second.val, first.val];
return head;
}
module.exports = { swapNodes };
Remove Nth Node From End of List asks to remove the nth node from the end, in one pass. Same fixed-gap idea as Swapping Nodes, but the gap is used to land on the node just before a deletion point instead of a node to swap.
A dummy node placed in front of head handles removing the head itself cleanly, without a special case. fast advances n + 1 steps ahead of slow, both starting at the dummy, then both slide forward together, one step each, until fast runs off the end. The gap between them stays n + 1 the whole time, so when fast becomes null, slow is sitting exactly one node before the one that needs removing.
Take head = [1, 2, 3, 4, 5], n = 2. fast advances 3 steps from the dummy, landing on node 3. Then both slide together.
step fast slow
0 3 dummy
1 4 1
2 5 2
3 null 3
slow ends at node 3, and slow.next is node 4, the 2nd from the end, exactly the one to remove. slow.next = slow.next.next skips over it, giving [1, 2, 3, 5].
// Remove Nth Node From End of List
// https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
//
// Problem: given the head of a linked list, remove the nth node
// from the end and return the head, in one pass.
//
// Same fixed-gap idea as Swapping Nodes, no length to compute an
// index from, so a gap is used instead. A dummy node in front of
// head handles the edge case of removing the head itself. Advance
// one pointer n + 1 steps ahead of the other, both starting at the
// dummy, then slide both forward together until the front one runs
// off the end, the back one lands exactly on the node just before
// the one to remove.
function removeNthFromEnd(head, n) {
const dummy = { val: 0, next: head };
let fast = dummy;
let slow = dummy;
for (let i = 0; i < n + 1; i++) {
fast = fast.next;
}
while (fast !== null) {
fast = fast.next;
slow = slow.next;
}
// slow is the node just before the one being removed.
slow.next = slow.next.next;
return dummy.next;
}
module.exports = { removeNthFromEnd };
Intersection of Two Linked Lists gives two lists that may merge into a shared tail, and asks for the node where they intersect, or null if they never do. The two lists can differ in length before the shared part starts, so walking both from their own heads at the same speed won’t line up at the intersection, one pointer would reach it before the other.
The fix: whenever a pointer reaches the end of its own list, redirect it to the head of the other list. That swap is what equalizes things, each pointer ends up walking its own list’s unique part plus the other list’s unique part plus the shared part, the exact same total distance for both, so they arrive at the intersection together instead of offset by the length difference.
Take listA = [4, 1, 8, 4, 5] and listB = [5, 6, 1, 8, 4, 5], sharing the tail 8 -> 4 -> 5. pointerA and pointerB start at their own heads, switching to the other list’s head the moment either runs out.
step pointerA pointerB
0 4 5
1 1 6
2 8 1
3 4 8
4 5 4
5 null 5
6 5 (B) null
7 6 4 (A)
8 1 1
9 8 8
pointerA and pointerB land on the same node, 8, on step 9, the actual intersection.
// Intersection of Two Linked Lists
// https://leetcode.com/problems/intersection-of-two-linked-lists/description/
//
// Problem: given the heads of two singly linked lists that may
// merge into a shared tail, return the node where they intersect,
// or null if they never do. Compare by reference, not value.
//
// The two lists can have different lengths before the shared part
// starts, so walking both from their own heads at the same speed
// won't line them up. The fix: when a pointer reaches the end of
// its own list, redirect it to the head of the other list. That
// swap equalizes the total distance both pointers travel by the
// time they'd reach the intersection, so they arrive there
// together instead of offset by the length difference.
function getIntersectionNode(headA, headB) {
let pointerA = headA;
let pointerB = headB;
while (pointerA !== pointerB) {
pointerA = pointerA ? pointerA.next : headB;
pointerB = pointerB ? pointerB.next : headA;
}
// Either the intersection node, or both null together if the
// lists never intersect at all.
return pointerA;
}
module.exports = { getIntersectionNode };
Palindrome Linked List asks whether a linked list reads the same forwards and backwards, in O(1) extra space. Same three phases as Reorder List, find the middle, reverse the second half, but the third phase compares instead of merges, Valid Palindrome’s fail-on-first-mismatch logic applied to two pointers walking in lockstep instead of converging from opposite ends of a string.
One deliberate difference from Middle of the Linked List’s loop: the condition here is fast.next && fast.next.next, not fast && fast.next. That’s what makes slow stop at the end of the first half rather than on the middle node itself, so the comparison phase only ever compares the two true halves against each other, never a middle node against nothing.
Take 1 -> 2 -> 2 -> 1. Finding the split: slow ends at the first 2. second = reverse(slow.next) reverses 2 -> 1 into 1 -> 2.
first second match?
1 1 yes
2 2 yes
second runs out after two comparisons, nothing failed, the list is a palindrome.
// Palindrome Linked List
// https://leetcode.com/problems/palindrome-linked-list/description/
//
// Problem: given the head of a linked list, determine whether it
// reads the same forwards and backwards, in O(1) extra space.
//
// Same three-phase idea as Reorder List, find the middle, reverse
// the second half, then compare, this time with Valid Palindrome's
// compare-and-fail-fast logic instead of a merge. One difference in
// the middle-finding loop: it checks fast.next and fast.next.next,
// not fast and fast.next, so that slow stops at the end of the
// first half rather than landing on the middle node itself, which
// keeps the comparison correct for both odd and even lengths.
function reverse(node) {
let prev = null;
while (node) {
const next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
function isPalindrome(head) {
if (!head || !head.next) return true;
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
let second = reverse(slow.next);
let first = head;
while (second) {
if (first.val !== second.val) return false;
first = first.next;
second = second.next;
}
return true;
}
module.exports = { isPalindrome };
Revisiting Hashing with Linked List technique
Happy Number already got a full walkthrough in the Hashing chapter’s Seen Before bucket, using a set to catch a repeated value. Worth returning to now that cycle detection has a name, the sequence of computed values, n, next(n), next(next(n)), and so on, is really an implicit linked list, each value’s “next” is just whatever the digit-squaring step produces. Floyd’s applies to it exactly the way it applies to a real linked list, trading the set’s O(n) space for two pointers at O(1).
Take n = 19, slow and fast both starting at 19, slow advancing one step at a time, fast two.
step slow fast
1 82 68
2 68 1
3 100 1
4 1 1
They meet at 1, which is the only way this loop can end at 1, since 1’s own next value is always 1 again, a self-loop. Meeting anywhere else would mean the sequence found a cycle that never reaches 1, exactly what happened for n = 2 back in the Hashing chapter’s trace.
// Happy Number, revisited with Floyd's instead of a set
// https://leetcode.com/problems/happy-number/description/
//
// Same problem solved in the Hashing chapter with a set tracking
// every value seen. The sequence of computed values is really an
// implicit linked list, each value's "next" is whatever
// sumOfSquaredDigits produces from it, so the exact same cycle
// detection used on real linked lists applies here too, trading the
// set's O(n) space for two pointers at O(1).
function sumOfSquaredDigits(n) {
let sum = 0;
while (n > 0) {
const digit = n % 10;
sum += digit * digit;
n = Math.floor(n / 10);
}
return sum;
}
function isHappy(n) {
let slow = n;
let fast = n;
do {
slow = sumOfSquaredDigits(slow);
fast = sumOfSquaredDigits(sumOfSquaredDigits(fast));
} while (slow !== fast);
// They only ever meet at 1 (a self-loop) or somewhere inside
// the non-happy cycle. Meeting at 1 is the only happy case.
return slow === 1;
}
module.exports = { isHappy };