Pattern Recognition for Algorithms

This guide starts from one habit I want for every problem I come across. See a problem, and before any code, say which pattern it belongs to and why. NeetCode 250 is my reference for which patterns to cover, but the problems worked through here can come from anywhere. Knowing what an algorithm does is the easier half. The harder half is the specific signal in a problem statement that makes the right one come to mind.

The Decision Tree page is where to start with a problem cold. It asks a small number of questions about the statement and narrows down which pattern to open first. Each chapter after it goes deep on one pattern, split into three pages that follow one order, recognize, write, practice.

Asking the Right Questions is the page I care about most. It works through five problems, reading each statement for the words that give the pattern away and the logic that confirms it. It contains no code and no analysis of running time, only the logic that takes a statement to a pattern, including how to tell the pattern apart from its closest neighbors.

Implementation answers how the code looks once the pattern is known. These are the skeletons worth knowing from memory, so that recognizing the pattern is the only hard part left and writing it becomes mechanical.

Examples works through problems one at a time, with the reasoning and the code together. Some reframe the problem first, and some are not on NeetCode 250 at all, since a pattern’s difficulty range is wider than any one list.

Hashing, Two Pointers, Sliding Window, Binary Search, and Stack are written so far. More patterns follow the same shape as they get written.

Decision Tree

Every other page in this guide assumes a pattern has already been picked, and digs into when that specific pattern fits and how its code looks. This page is the step before that, reading a problem cold and narrowing down which pattern to even consider, before opening any single chapter.

It can only ever reflect the chapters that already exist. Right now that’s Hashing, Two Pointers, Sliding Window, Binary Search, and Stack. This page gets revisited and expanded every time a new pattern is added, sometimes a new pattern will split an earlier question further than it’s split today.

Question 1: does the problem only care about values, not position?

If the only thing that matters is whether a value exists, how many times it occurs, or what other value completes it, and order or position never enters the question, that points to Hashing.

If position, order, or a contiguous run of elements matters, move to the next question.

Question 2: is it about a contiguous run, with a min or max being asked over that run?

“Longest substring,” “smallest subarray,” “maximum sum of a window of size k,” anything where the elements have to sit next to each other in the original array or string, not any subset.

The contiguous run is not always written in the statement. A problem can ask for a maximum or minimum and never mention a subarray, and still have a hidden window. Cards taken from the two ends of a row leave a contiguous block in the middle. Elements that can only be raised, with a goal of making several equal, become a stretch of the array once sorted. A condition on the count of one kind of element, like exactly k odd numbers, gives a window over the positions of those elements. If the statement asks for a max or min and has no contiguous run, ask what is left behind, whether sorting groups the elements that matter, and whether a list of positions holds the structure, before ruling this question out. The Sliding Window chapter covers these in Question 5.

If yes, check one more thing before committing: does growing the run always push whatever’s being tracked in one predictable direction? A sum only ever needs non-negative values for this to hold, since growing the window would otherwise sometimes help and sometimes hurt, with no guarantee that shrinking from the left is ever the right move to fix a violation. A frequency or distinct-count constraint tends to hold this naturally, removing an element from the left can only reduce a count, never increase it unexpectedly.

If that monotonic direction holds, this is Sliding Window. If it doesn’t hold, a contiguous-run question that looks like sliding window at a glance, like a subarray sum target with negative numbers allowed, isn’t actually solvable that way, and points back toward Hashing instead, prefix sums paired with a frequency map.

If the problem isn’t about a contiguous run at all, move to the next question.

Question 3: does it involve two ends of ordered data, or relative position and speed through a sequence, with no aggregate needed over a whole range?

Two ends of a sorted array converging inward, a read/write pointer compacting an array in place, or two pointers moving through a linked list at different speeds. None of these ever need to know something about an entire range at once, only the values or positions the pointers currently sit on.

If yes, that’s Two Pointers.

If the problem doesn’t reduce to two positions moving with no aggregate needed, move to the next question.

Question 4: does a guess anywhere in the search space let you discard the rest of it without checking each one?

This holds whenever the data is sorted, or whenever some condition on a candidate answer is monotonic, false up to a point and true from there on, or the reverse. Checking one guess and finding it too small or too big tells you every guess on the wrong side is settled too, no need to look at them individually. That’s not limited to searching a sorted array for a value, it also covers guessing an answer, a capacity, a speed, a distance, and checking whether that guess is feasible.

If yes, that’s Binary Search.

If no guess settles a whole side, move to the next question.

Question 5: does some element’s answer depend on something that comes later, and does the latest waiting element get decided first?

Read the input left to right and ask, for each element, whether it can be decided with only what has been read so far. An opening bracket cannot, it needs its closer. A day waiting for a warmer day cannot, the warmer day is ahead. A bar in a histogram cannot know where its rectangle ends until a shorter bar arrives. Those elements wait.

Then check the order they get decided in. If an arriving element always decides the most recent waiting one first, stopping at the first one it cannot decide, a closer matching the latest open bracket, a warm day answering the coldest waiting day, that is Stack. The wording cues are nested or matched items, cancellations, and “next greater”, “previous smaller”, “how far until”, or “how far back”. If the oldest waiting element is decided first instead, it is a queue, and if elements leave from both ends, as in Sliding Window Maximum, it is a deque.

Still open

Everything past here, a decision that depends on subproblems rather than a single pass, doesn’t have a question here yet. That’s what the chapters after Stack will need to fill in.

Hashing: Asking the Right Questions

Seeing it in a statement

Every problem statement has two parts. What it asks for, the shape of the answer. What it offers, the structure in the input we can lean on. The pattern is where the two meet.

If the order of the input changes the answer, it is not hashing. Check Two Pointers or Sliding Window.

Five problems follow, each read from its statement to the pattern. No code here, the code lives in Implementation and Examples.

1. Contains Duplicate II

The statement. Contains Duplicate II gives an array nums and a number k, and asks whether two different indices i and j hold the same value with i and j at most k apart.

Asks for. Whether a value repeats within k positions.

Offers. Values that can be filed by themselves, with the last index stored under each. The distance is a condition checked after the lookup, so the core ask is Seen Before.

Why it fits. The plain approach looks back from every element, up to k positions, for an equal value, the same search repeated once per element. A map from each value to the last index it appeared at replaces that search. On reaching a value, look it up, and if its last index is within k, the answer is yes. If not, overwrite the stored index with the current one. Only the last index matters, since any earlier occurrence is even further away.

Position matters in this problem, but it is what gets stored under the key, not the key itself. The same problem can also be read as a window of size k holding a set of values, which is hashing and sliding window working together.

2. First Unique Character in a String

The statement. First Unique Character in a String gives a string and asks for the index of the first character that appears exactly once, or -1 if there is none.

Asks for. The first character that appears exactly once.

Offers. Characters whose counts do not depend on order. “Exactly once” is a count, so this is Frequency.

Why it fits. A character’s count is not known until the whole string has been read, since a character that looks unique halfway through can repeat at the very end. So the counts come first, from the full string, with the character as the key. Then the string is walked again in its original order, and the first character whose count is 1 is the answer.

The word “first” brings order back, and that is the part worth noticing. Order decides which unique character to report, but it plays no part in the counts. Shuffling the string changes the answer’s index and leaves every count the same, so the counting is pure hashing and the order is only a final filter.

3. Pairs of Songs With Total Durations Divisible by 60

The statement. Pairs of Songs With Total Durations Divisible by 60 gives a list of song durations and asks how many pairs of songs have a total duration divisible by 60.

Asks for. The number of pairs whose sum is divisible by 60.

Offers. A condition that depends only on remainders. Each song needs a partner with a matching remainder, so this is Pairing.

Why it fits. The partner is not one fixed value, as it is in Two Sum. Whether a sum is divisible by 60 depends only on the two remainders after dividing by 60. A song with remainder 20 needs a partner with remainder 40, and a song with remainder 0 needs another with remainder 0. So the key is the remainder, and what is stored under it is how many songs with that remainder have been seen. Each new song adds the stored count of its partner’s remainder to the total.

Sorting the durations does not help, which rules out two pointers. A longer song says nothing about its remainder, so position in a sorted list carries no information about which songs pair up. Shuffling the list leaves the count unchanged.

4. Group Anagrams

The statement. Group Anagrams gives a list of strings and asks for them grouped so that anagrams of each other end up together.

Asks for. Strings grouped together.

Offers. A shared form, the sorted letters, that every anagram has. A shared form is a key, so this is Grouping.

Why it fits. Grouping needs a key that every member of a group shares and no outsider has. Two strings are anagrams exactly when they have the same letters in the same counts, so the sorted letters of a string work as the key, and so does its count of each letter. The check for any grouping key is that two items map to the same key if and only if they belong together. Here both directions hold, so every string files itself under its key and each key collects one group. Nothing about the order of the input list matters.

5. Longest Consecutive Sequence

The statement. Longest Consecutive Sequence gives an unsorted array and asks for the length of the longest run of consecutive values, such as 1, 2, 3, 4, wherever those values sit in the array.

Asks for. The longest run of consecutive values.

Offers. An unsorted array where position means nothing. “Longest” and “sequence” suggest a window, but “consecutive” is about values, not positions. The real ask is whether n + 1 exists anywhere, which is Seen Before.

Why it fits. Put every value in a set. A run can only start at a value whose n - 1 is missing, since otherwise the run would extend further down. From each such start, keep asking whether the next value is in the set, and the count of successful asks is the run’s length. A window is ruled out because the input order means nothing, and the shuffle test confirms it, any shuffle of the array has the same answer.

What the five share

Each statement asks one of four things about a value, has it been seen, how many times, what completes it, or what it belongs with. Each has a key that can be named, the value, the character, the remainder, the sorted letters, the number itself. And in each, the input’s order is either irrelevant or used only after the hashing is done, as a stored index in the first problem and a final filter in the second. When order starts deciding the answer itself, the Decision Tree points to Two Pointers or Sliding Window.

Implementation

A hash map is key-value storage. Give it a key and it hands back the value stored under that key, and the cost of a read or a write stays the same no matter how many keys it already holds. Once a problem is recognized as one of the four kinds from Asking the Right Questions, the code follows a fixed shape. These are the four skeletons, one per kind, worth knowing from memory rather than re-derived each time.

Hash maps in JavaScript

JavaScript has three structures that are the same key-value idea, shaped for different needs.

Object is the plain version. Keys are coerced to strings, and it is what most people reach for first without thinking of it as a hash map.

Map is the general-purpose version. Any value can be a key, insertion order is preserved, and it has a proper .has(), .get(), .set() interface. It is the right choice whenever both a key and a value attached to it are needed, like frequency counts.

Set is a hash map with the value dropped. It stores only keys and answers one question, .has(key). It is the right choice whenever the value would be meaningless and all that matters is whether the key exists, which is the Seen Before kind.

Seen Before

function seenBefore(items) {
    const seen = new Set();
    for (const item of items) {
        if (seen.has(item)) return true; // already ran into this one
        seen.add(item);
    }
    return false;
}

Frequency

function frequency(items) {
    const counts = new Map();
    for (const item of items) {
        counts.set(item, (counts.get(item) || 0) + 1);
    }
    return counts;
}

Pairing

function pairing(nums, target) {
    const seen = new Map(); // value -> index
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (seen.has(complement)) return [seen.get(complement), i];
        seen.set(nums[i], i);
    }
    return [];
}

The check happens before the insert, not after. That order matters, it is what stops a value from pairing with itself.

Grouping

function grouping(items, keyFn) {
    const groups = new Map();
    for (const item of items) {
        const key = keyFn(item);
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(item);
    }
    return [...groups.values()];
}

keyFn is whatever computed property decides which bucket an item belongs to, a count of each letter for anagrams, a sequence of letter gaps for shifted strings, a plain number like a loss count, whatever the problem defines as “belongs together.”

Not every grouping problem fits one key per item, though. Valid Sudoku checks each item against three keys at once, its row, its column, and its box, which means checking and updating three separate group-sets per item instead of looking up one key in one map:

function groupingMultiKey(items, keysFn) {
    const groups = new Map(); // one Set per possible key

    for (const item of items) {
        const keys = keysFn(item); // e.g. [row, col, box] for one cell

        for (const key of keys) {
            if (!groups.has(key)) groups.set(key, new Set());
            if (groups.get(key).has(item)) return false; // already in this group
            groups.get(key).add(item);
        }
    }

    return true;
}

Hashing: Examples

Worked problems from the questions chapter, reasoning and code together, one bucket at a time.

Seen Before

Contains Duplicate hands us an array and asks a single question, does any value in it show up more than once. Nothing about order matters, nothing about position matters, the only thing that matters is whether a value repeats anywhere in the array.

The naive way to answer that is to pick a value and check it against every other value in the array, then move to the next value and do the same thing again. That works, but it means for every single element we are re-reading the whole array to answer one yes-or-no question. The work we redo on every step is identical in shape, “is this value present among the ones I have already looked at.”

That repeated shape is the tell. If the question we keep re-asking is always “have I already looked at this value,” we do not need to re-read anything, we just need to remember what we have already looked at. That is exactly what a hash map gives us, a place to record every value the moment we look at it, and a way to check that record in one step instead of a scan.

So the approach becomes: walk the array once, and for each value, first ask the map if it already holds this value. If it does, we have our duplicate and we are done, no need to look further. If it does not, we record it in the map and move to the next value. By the time we reach any given element, the map contains every element that came before it, so checking the map is the same as checking the whole array up to that point, except it costs one lookup instead of a scan. That is why the seen-before question maps directly onto this problem, and why the fix for the repeated O(n) scan is a single hash map built as we go.

// Contains Duplicate
// https://leetcode.com/problems/contains-duplicate/description/
//
// Problem: given an array of integers, return true if any value
// appears at least twice, and false if every element is distinct.
//
// The hint toward a hash map is "appears at least twice" itself,
// that phrase is really asking, for each value: have I run into
// this value already? That is the "Seen Before" intuition, so a
// hash set is the fit, one lookup instead of re-scanning the array.

function containsDuplicate(nums) {
    // A Set, not a Map, because we never need a value attached to
    // the key. All we ever ask is "does this key exist," so a Map
    // here would just be storing a throwaway value like true next
    // to every key. Set is the key-only shape of a hash map.
    const seen = new Set();

    for (const n of nums) {
        // Ask the set first. If it already holds this value,
        // we found our duplicate, no need to look any further.
        if (seen.has(n)) return true;

        // Otherwise this is the first time we've seen n.
        // Record it so future values can check against it.
        seen.add(n);
    }

    // Walked the whole array, every value was new when we reached it.
    return false;
}

module.exports = { containsDuplicate };

Contains Duplicate II asks the same seen-before question with one more condition attached, a repeat only counts if the two indices are within k of each other. So “have I seen this value” is not enough on its own anymore, we also need to know where we saw it.

That changes what the map has to hold. Instead of a set that only answers yes or no, we need a map from value to the index it last appeared at. The check on each element becomes two parts, has this value shown up before, and if so, is the gap between here and there small enough to count.

The map still gets written to on every element, whether or not that element triggers a match, because a value seen too far back to count now might still be close enough to count against a later index. Overwriting the last-seen index each time keeps the stored position as recent as possible, which is exactly what the distance check needs.

// Contains Duplicate II
// https://leetcode.com/problems/contains-duplicate-ii/description/
//
// Problem: given an array of integers and an integer k, return true
// if there are two distinct indices i and j such that nums[i] ==
// nums[j] and the distance between i and j is at most k.
//
// Strip away the k constraint for a moment and this is just Contains
// Duplicate again, does any value repeat (that's what nums[i] == nums[j] means right?) , answered by remembering
// every value we pass. The k constraint doesn't change that core
// question, it only restricts which repeats are allowed to count.
// A far-apart repeat is not a match here, so knowing a value repeated
// is no longer enough, we also need to know how far apart the two
// occurrences are. That means the map can't just record "seen or
// not," it has to record the index each value was last seen at, so
// the distance can actually be checked when a repeat shows up.

function containsNearbyDuplicate(nums, k) {
    const lastSeenAt = new Map(); // value -> most recent index

    for (let i = 0; i < nums.length; i++) {
        const n = nums[i];

        if (lastSeenAt.has(n) && i - lastSeenAt.get(n) <= k) {
            return true;
        }

        // Record (or overwrite) this value's most recent position,
        // so the next repeat only measures distance from here.
        lastSeenAt.set(n, i);
    }

    return false;
}

module.exports = { containsNearbyDuplicate };

Longest Consecutive Sequence gives an unsorted array and asks for the length of the longest run of consecutive integers hiding inside it, in O(n) time. “Consecutive” here means back to back on the number line, not back to back in the array. Take [100, 4, 200, 1, 3, 2], scattered in that order, but 1, 2, 3, 4 sit next to each other once we think in terms of value rather than position, and no longer run in the array beats that, so the answer is 4.

Sorting first would make the run easy to spot, [1, 2, 3, 4, 100, 200] has the run sitting right next to itself, but sorting itself already costs O(n log n), which rules it out before we even get to the counting.

Without sorting, we still have to figure out which numbers keep the consecutive sequnce going, and the only tool we start with is the raw array. Take 1 from our example array. To know the run keeps going, we need to know whether 2 shows up anywhere in [100, 4, 200, 1, 3, 2], which means scanning the array looking for it. It does, so we check for 3 the same way, another full scan, then 4, another scan, then 5, one more scan that comes back empty and stops the run there.

That is four scans just to measure the run starting at 1. Now consider that we do not know in advance where a run starts, so in the worst case this same scan-for-the-next-number step gets repeated starting from every single number in the array. Each of those scans costs O(n) on its own, and we potentially do one for every element, which multiplies out to O(n^2) overall, the exact cost we were trying to avoid by skipping the sort.

Look at what actually got repeated across all those scans: the same question, is this specific number present in the array, asked over and over with a different number each time. Answering it by scanning costs O(n) per question, and we are asking it many times, which is where the O(n^2) comes from. What we need instead is a way to answer that same question in one step, not a scan.

That means recording every number somewhere we can check instantly, before doing any counting. A set does exactly that, so put every number in the array into a set first. After that, asking “is n + 1 present” is a single lookup, not a search across the array, the same fix that turned Contains Duplicate from a scan into a seen-before check.

This puts the solution in two separate passes. The first pass walks the original array once, just to load every number into the set. The second pass walks the set, not the array, doing the actual counting. Iterating the set instead of the array also means a number that appears more than once in the input only gets processed once, since the set already collapsed it to a single entry.

That alone still leaves a second problem, counting from every number would recount the same run many times, once from each of its members. Take 1, 2, 3, 4 from the example, if we counted forward from 1, then again from 2, then again from 3, we would redo the same run three extra times.

The fix is to make each number disappear from the set the moment it gets counted. Walk the set, and for a number still there, delete it, then expand outward from it, right first, then left, deleting every neighbor as it gets pulled into the run. A number that already got absorbed into an earlier run is already gone from the set by the time the outer walk would have reached it, and a set’s iterator skips entries that were already deleted, so it is simply never visited a second time. Every number gets deleted exactly once, and every deletion happens during exactly one expansion, so the total work across every run put together is still O(n).

// Longest Consecutive Sequence
// https://leetcode.com/problems/longest-consecutive-sequence/description/
//
// Problem: given an unsorted array of integers, return the length of
// the longest run of consecutive integers, in any order in the input,
// solved in O(n) time.
//
// The seen-before question here is "is this value present in the
// array at all," asked over and over as we try to extend a run.
// A set answers that in one lookup instead of a scan, which is what
// keeps the whole thing linear.

function longestConsecutive(nums) {
    // This is the first pass, even though there's no visible loop.
    // Set(nums) walks nums once internally to load every value in.
    const present = new Set(nums);
    let longest = 0;

    // Second pass, over the set, not nums, so a value repeated in
    // the input only gets processed once here.
    for (const n of present) {
        // No need to check whether n was already claimed by an
        // earlier run. If it was, it was deleted below before this
        // loop reached it, and a Set's iterator skips entries that
        // were already deleted, so n simply never shows up here.
        present.delete(n);
        let length = 1;

        // Expand right, deleting each number as it joins this run so
        // no later iteration step processes it again.
        let right = n + 1;
        while (present.has(right)) {
            present.delete(right);
            length++;
            right++;
        }

        // Expand left the same way.
        let left = n - 1;
        while (present.has(left)) {
            present.delete(left);
            length++;
            left--;
        }

        longest = Math.max(longest, length);
    }

    return longest;
}

module.exports = { longestConsecutive };

Happy Number gives a positive integer and a rule, replace the number with the sum of the squares of its digits, then do it again to whatever comes out, and again. If this process ever reaches 1, the number is happy. Take 19: 1^2 + 9^2 = 82, then 8^2 + 2^2 = 68, then 6^2 + 8^2 = 100, then 1^2 + 0^2 + 0^2 = 1. Reached 1, so 19 is happy.

I know it is not very intuitive to know that this problem demands a map, but here’s the spoiler : Loop only ends one of two ways, n reached 1, or n repeated.

Not every number does become 1 at the end. Take 2: 4, 16, 37, 58, 89, 145, 42, 20, 4. Look at the last value, 4, it already showed up earlier in this same sequence. From here on, applying the same rule to 4 produces the exact same sequence all over again, 16, 37, 58, forever. It will never reach 1, but nothing in the rule itself says when to give up and answer no.

That is the actual problem hiding in this one. The rule only tells us how to compute the next number, it never tells us when to stop. Without some way to notice a repeat, the only way to be sure a number is not happy is to keep applying the rule forever, which is not something a program can do.

A repeat is exactly what we can catch with a seen-before check, just applied to computed values instead of array elements. Keep a set of every value produced so far. Before computing the next one, check whether the current value is already in the set, if it is, the sequence has looped back on itself and will never reach 1, so we stop and answer no. If it reaches 1 first, we stop and answer yes. Either way, the seen-before check is what turns “keep going forever” into a guaranteed stopping point.

// Happy Number
// https://leetcode.com/problems/happy-number/description/
//
// Problem: given a positive integer, repeatedly replace it with the
// sum of the squares of its digits. If this process reaches 1,
// the number is happy. If it loops forever without ever reaching 1,
// it is not happy. Determine which case a given number falls into.
//
// The seen-before check here isn't spotting a duplicate in an array,
// it's spotting a cycle. If a value we computed before ever shows up
// again, we are back on a path we already walked, and walking it
// again can only produce the same values in the same order forever.
// That repeat is the only signal telling us to stop and say "no."

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) {
    const seen = new Set();

    while (n !== 1 && !seen.has(n)) {
        seen.add(n);
        n = sumOfSquaredDigits(n);
    }

    // Loop only ends one of two ways, n reached 1, or n repeated.
    return n === 1;
}

module.exports = { isHappy };

Frequency

Valid Anagram gives two strings and asks whether the second is an anagram of the first, meaning it uses the exact same letters, the exact same number of times each, just arranged differently. "anagram" and "nagaram" are anagrams. "rat" and "car" are not, even though both are three letters, because the letters themselves don’t match.

Order plays no role in the answer at all, which is the first thing worth noticing. Whatever approach we use has to somehow throw away position and only compare, for each letter, how many times it shows up. That is a frequency question, not a seen-before question, “does the letter a show up twice in both strings” is a different thing to check than “does the letter a show up at all.”

One way to answer that without extra structure is to sort both strings and compare them letter by letter. Two strings with the same letters in the same quantities become identical once sorted, "anagram" and "nagaram" both sort to "aaaagmnr". That works, but sorting costs O(n log n), and we are only using the sort to line up matching letters, not because order matters to the actual answer.

A frequency map gets the same answer without sorting. Count how many times each letter appears in the first string. Then walk the second string, and for each letter, subtract one from that letter’s count instead of adding. If the two strings really do have matching letters in matching amounts, every subtraction lands on a count that was already there waiting to be used up, and by the end every count reaches exactly zero.

Two failures fall out of that same process on their own. If the second string contains a letter the first string never had, there is no count to subtract from, an immediate mismatch. If a count is left over above zero once the second string runs out, the first string had more of that letter than the second string used, also a mismatch. Deleting a letter’s entry the moment its count hits zero means that at the end, an empty map is itself the proof that everything matched, nothing extra is left over on either side.

// Valid Anagram
// https://leetcode.com/problems/valid-anagram/description/
//
// Problem: given two strings s and t, return true if t is an
// anagram of s, meaning t uses exactly the same letters as s,
// the same number of times each, just possibly in a different order.
//
// This is a frequency question: does every letter show up the same
// number of times in both strings. Count the letters of s, then walk
// t subtracting from those counts. If everything cancels out exactly,
// the two strings had matching letter counts all along.

function isAnagram(s, t) {
    // Different lengths can never be anagrams, and checking this
    // first means the counting below never has to handle it.
    if (s.length !== t.length) return false;

    const counts = new Map();
    for (const ch of s) {
        counts.set(ch, (counts.get(ch) || 0) + 1);
    }

    for (const ch of t) {
        // t contains a letter s never had at all.
        if (!counts.has(ch)) return false;

        const remaining = counts.get(ch) - 1;
        if (remaining === 0) {
            // This letter's count from s is now fully used up by t.
            counts.delete(ch);
        } else {
            counts.set(ch, remaining);
        }
    }

    // If every letter cancelled out exactly, nothing is left.
    return counts.size === 0;
}

module.exports = { isAnagram };

Ransom Note gives a ransom note string and a magazine string, and asks whether the note can be built entirely by cutting letters out of the magazine, using each letter in the magazine at most once. If the note needs two es, the magazine has to have at least two es to give up.

This looks close to Valid Anagram, both come down to counting letters, but the relationship between the two strings is different in a way that matters. Valid Anagram asks whether two strings have exactly matching letter counts, the same amount of everything on both sides. Ransom Note only asks whether one string’s counts are enough to cover the other’s, the magazine is allowed to have letters left over that the note never touches.

That difference changes what the frequency map gets used for. Build it from the magazine, one count per letter available. Then walk the note, and for each letter, check whether the map still has any of it left. If it does, spend one, subtract from the count. If it doesn’t, either the letter never appeared in the magazine at all or every copy of it has already been spent by an earlier letter in the note, either way the note cannot be built and we stop right there.

Notice what we do not check here. Valid Anagram ends by confirming the map is completely empty, because leftover counts on either side meant a mismatch. Ransom Note never checks that, a magazine with 10 unused letters after the note is fully built is still a valid build, those letters just never got used. The only thing that fails the whole problem is running out of a letter the note still needs, which is exactly the one check the loop performs.

// Ransom Note
// https://leetcode.com/problems/ransom-note/description/
//
// Problem: given a ransom note string and a magazine string, return
// true if the note can be built entirely out of letters from the
// magazine, using each letter in the magazine at most once.
//
// Count the letters available in the magazine, then walk the note
// spending from those counts. Unlike Valid Anagram, the magazine is
// allowed to have leftover letters, so we never check that anything
// hits exactly zero, only that we never spend a letter that isn't
// there to spend.

function canConstruct(ransomNote, magazine) {
    const available = new Map();
    for (const ch of magazine) {
        available.set(ch, (available.get(ch) || 0) + 1);
    }

    for (const ch of ransomNote) {
        const remaining = available.get(ch) || 0;

        // Nothing left of this letter to spend.
        if (remaining === 0) return false;

        available.set(ch, remaining - 1);
    }

    return true;
}

module.exports = { canConstruct };

Majority Element gives an array and asks for the value that appears more than half the time, more than n / 2 times in an array of size n. The problem guarantees one always exists, so there’s no case to handle where nothing qualifies.

The frequency map here is the plainest version of the pattern so far, count how many times each value appears, same as every problem in this section. What’s worth noticing is what the threshold itself guarantees. Since more than half the array can only ever belong to one value, at most one value can ever cross that line, there is no risk of two different values both racing past n / 2.

That guarantee means the count doesn’t need to finish before it gets used. Update a value’s count on every element, and the instant one crosses the threshold, return it immediately, no second pass over the map needed to go find the winner afterward, and no need to keep counting the rest of the array once the answer is already known.

// Majority Element
// https://leetcode.com/problems/majority-element/description/
//
// Problem: given an array of size n, return the element that appears
// more than n / 2 times. The problem guarantees one always exists,
// so there's no need to handle the case where nothing qualifies.
//
// Count each value as we go, and the moment any single value's count
// crosses n / 2, that value has to be the answer, since more than
// half the array can only belong to one value at a time.

function majorityElement(nums) {
    const counts = new Map();
    const majorityThreshold = nums.length / 2;

    for (const n of nums) {
        const count = (counts.get(n) || 0) + 1;
        counts.set(n, count);

        // No need to finish counting everything else once one value
        // has already crossed the threshold, it's the only one that
        // can, so we can return the moment it happens.
        if (count > majorityThreshold) return n;
    }
}

module.exports = { majorityElement };

Determine if Two Strings Are Close is the first Medium in this bucket, the three problems above are all Easy. Two strings are “close” if the letters and their counts can be reshuffled among each other to turn one string into the other, nothing added, nothing removed, just handed out differently. Take word1 = "cabbba" and word2 = "abbccc". word1 has counts a: 2, b: 3, c: 1. word2 has counts a: 1, b: 2, c: 3. The counts attached to each letter differ, but both strings use the same three letters, a, b, c, and both use the same three counts, 1, 2, 3, just assigned to different letters. That is exactly what makes these two close.

Both operations only rearrange things among characters that already exist in the string, neither one can introduce a new character, remove one, or change how many letters the string has in total. That last part gives a free check before doing anything else, two strings of different lengths can never be close, no reshuffling changes a string’s length, so a length mismatch rules out the pair immediately.

Past that, the rest splits into two separate frequency checks rather than one.

First, the same set of characters has to be present in both strings. Swapping counts or swapping identities never adds or removes a character, it only moves things around among what’s already there, so if one string uses a character the other doesn’t, no sequence of operations closes that gap.

Second, given matching character sets, the swap-the-counts operation means any character’s count can end up attached to any other character. So checking count against count for the same character, a in word1 against a in word2, is checking the wrong thing, since which character holds which count can move freely. What has to match is the multiset of counts overall, and rather than sorting both lists of counts to compare them, we can count how many characters share each count value, on both sides, and compare those two counts directly, a frequency map built on top of a frequency map. Word1’s counts were a: 2, b: 3, c: 1, so its count-of-counts is 1: 1, 2: 1, 3: 1, one character has each of the counts 1, 2, and 3. Word2’s counts were a: 1, b: 2, c: 3, count-of-counts 1: 1, 2: 1, 3: 1, the same. That match is what confirms the two strings are close, without sorting either list.

// Determine if Two Strings Are Close
// https://leetcode.com/problems/determine-if-two-strings-are-close/description/
//
// Problem: two strings are "close" if one can be turned into the
// other using any number of two operations, swap the counts of two
// existing characters, or swap the identity of two existing
// characters. Determine whether two given strings are close.
//
// Both operations only rearrange things among characters already
// present, they never introduce a new character or change how many
// distinct characters exist. So being close comes down to two
// separate frequency checks: the same set of characters has to be
// present in both strings, and the same multiset of counts has to
// be achievable, regardless of which character originally held
// which count.

function buildFrequencyMap(items) {
    const counts = new Map();
    for (const item of items) {
        counts.set(item, (counts.get(item) || 0) + 1);
    }
    return counts;
}

function mapsMatch(mapA, mapB) {
    if (mapA.size !== mapB.size) return false;
    for (const [key, value] of mapA) {
        if (mapB.get(key) !== value) return false;
    }
    return true;
}

function closeStrings(word1, word2) {
    // Reshuffling counts among existing characters can never change
    // how many letters a string has, so mismatched lengths can be
    // ruled out before building anything.
    if (word1.length !== word2.length) return false;

    const counts1 = buildFrequencyMap(word1);
    const counts2 = buildFrequencyMap(word2);

    // Same characters present, regardless of which count belongs
    // to which one, character identity itself can be swapped.
    for (const ch of counts1.keys()) {
        if (!counts2.has(ch)) return false;
    }
    if (counts1.size !== counts2.size) return false;

    // Same counts available, regardless of which character
    // originally held which count. Instead of sorting both lists of
    // counts and comparing them pairwise, count how many characters
    // share each count value, on both sides, and compare those two
    // frequency-of-frequency maps directly.
    const countOfCounts1 = buildFrequencyMap(counts1.values());
    const countOfCounts2 = buildFrequencyMap(counts2.values());

    return mapsMatch(countOfCounts1, countOfCounts2);
}

module.exports = { closeStrings };

Minimum Number of Operations to Make Array Empty is the second Medium in this bucket. One operation removes two or three copies of the same value from the array, and the question is the fewest operations needed to remove everything, or -1 if it can’t be fully emptied.

An operation only ever targets copies of one value, so the only thing that matters for any value is how many copies of it exist, not where they sit in the array. That’s the frequency map again, and once it’s built, the problem splits into one independent question per value: given a count c, what’s the fewest groups of 2 or 3 that sum to exactly c, and is that even possible.

c = 1 is the only count with no answer, no combination of 2s and 3s ever sums to 1. Every other count can be cleared, and the fewest operations comes from using as many 3s as possible. Split by c mod 3. c = 3n needs n groups of 3. c = 3n + 2 needs n groups of 3 plus one group of 2 for what’s left over. c = 3n + 1 is the one that needs care, a leftover of 1 isn’t removable on its own, so one group of 3 gets traded back, n - 1 groups of 3, and the 3 + 1 = 4 left over becomes two groups of 2, (n - 1) + 2 operations. Take c = 10, n = 3, remainder 1, so it’s 2 groups of 3 and 2 groups of 2, 3 + 3 + 2 + 2 = 10, four operations.

Every one of those three cases lands on n or n + 1 operations, which is exactly Math.ceil(c / 3). So the full solution is: build the frequency map, and for every count in it, return -1 immediately if any count is 1, otherwise sum Math.ceil(count / 3) across all of them.

// Minimum Number of Operations to Make Array Empty
// https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/description/
//
// Problem: given an array, one operation removes two or three copies
// of the same value. Return the minimum number of operations to
// empty the array, or -1 if it can't be done.
//
// Only "how many copies of each value exist" matters, position and
// order don't, so this starts with a frequency map. From there the
// problem splits into one independent question per value: given a
// count c, what's the fewest groups of 2 or 3 that sum to it, and is
// it even possible.
//
// c = 1 is the only impossible count, nothing sums to 1 using 2s
// and 3s. Past that, using as many 3s as possible and covering the
// remainder works out to ceil(c / 3) operations, by three cases:
//   c = 3n:     n groups of 3.
//   c = 3n + 2: n groups of 3, one group of 2 for the remainder.
//   c = 3n + 1: (n - 1) groups of 3, two groups of 2 for the
//               leftover 4, since a lone group of 1 isn't valid.
// All three land on n or n + 1 operations, which is ceil(c / 3).

function minOperations(nums) {
    const counts = new Map();
    for (const n of nums) {
        counts.set(n, (counts.get(n) || 0) + 1);
    }

    let operations = 0;
    for (const count of counts.values()) {
        if (count === 1) return -1;
        operations += Math.ceil(count / 3);
    }

    return operations;
}

module.exports = { minOperations };

Pairing

Two Sum gives an array and a target, and asks for the indices of the two numbers that add up to it. Exactly one valid pair exists in the input, and a number can’t be paired with itself.

The brute force is a nested loop, for each number, check every other number to see if the two add up to the target. That works, but not for an interview, because for every element it re-scans the rest of the array looking for one specific value, the number that would complete the sum. That specific value isn’t a mystery though, if the target is 9 and the current number is 4, the number we need is exactly 5, target - 4. We already know what we’re looking for before we look, which means the search itself is the wasted step, not the arithmetic.

If we know exactly what value would complete the pair, the only question left is whether that value showed up earlier in the array, which is a lookup, not a search, once we’ve been recording values as we go. So walk the array once, and at each number, first check whether its complement, target - nums[i], is already in a map of values we’ve seen. If it is, those two indices are the answer. If it isn’t, record the current value and move on.

The order of that check matters. Looking up the complement has to happen before the current value gets added to the map, otherwise a number could pair with itself, the map would already contain the very value we’re standing on. Checking first, inserting second, is what keeps every match built from two genuinely different positions in the array.

This is Pairing, not Seen Before, even though the map calls involved, has then set, are identical to Contains Duplicate’s. The difference is what gets looked up. Seen Before checks the current value against the map, asking whether this exact value showed up before. Two Sum never looks up the current value at all, it looks up target - nums[i], a value computed from the current one, asking whether something else exists that would complete it. That’s also why the self-pairing rule only shows up here, “does something else complete this” explicitly rules out a number completing itself, while “have I seen this” has no such restriction.

// Two Sum
// https://leetcode.com/problems/two-sum/description/
//
// Problem: given an array of integers and a target, return the
// indices of the two numbers that add up to the target. Exactly one
// valid pair exists, and the same element can't be used twice.
//
// For each number, the question is "does some other number in the
// array complete this one to the target." Rather than searching for
// that other number, we compute exactly what it would have to be,
// target - current, and check whether we've already recorded it.

function twoSum(nums, target) {
    const seenAt = new Map(); // value -> index

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        // Check before inserting, so nums[i] never pairs with
        // itself, only with a number that came before it.
        if (seenAt.has(complement)) {
            return [seenAt.get(complement), i];
        }

        seenAt.set(nums[i], i);
    }

    return [];
}

module.exports = { twoSum };

Subarray Sum Equals K gives an array and an integer k, and asks for the number of contiguous subarrays whose elements sum to exactly k. The brute force checks every possible subarray directly, re-summing overlapping ranges over and over, O(n^2) at best.

Take nums = [3, 4, -7, 1, 3, 3, 1, -4] and k = 7. Walk the array keeping a running total, the sum of everything seen so far, and write it down at every step, including a 0 before the array even starts.

index:         -    0    1    2    3    4    5    6    7
element:            3    4   -7    1    3    3    1   -4
running total: 0    3    7    0    1    4    7    8    4

The sum of any subarray that ends at some position and starts right after an earlier position is just the running total at the end minus the running total at that earlier point. Call the ending running total y and an earlier one x, the subarray between them sums to y - x. We want that to equal k, so y - x = k, which rearranges to x = y - k. At every step, the earlier running total that would complete a subarray summing to k is exactly y - k.

Two things show up walking this example that a simpler one would hide. First, at index 1 the running total is 7, y - k = 7 - 7 = 0, and 0 occurred once already, before the array started, which is the subarray [3, 4] summing to 7, one match. Second, at index 5 the running total is again 7, y - k = 0 again, but by now 0 has occurred twice, once at the start and once at index 2, so this single step contributes two matches at once, the subarrays [3, 4, -7, 1, 3, 3] and [1, 3, 3], both ending at index 5 and both summing to 7. That second case is exactly why the map has to store how many times each running total occurred, not just whether it occurred, a plain seen-before check would only ever report one match here, not two.

That’s the same pairing shape as Two Sum, checking whether something earlier completes the current value to a target, except the value being paired is a running prefix sum, not a raw array element, and the relationship is subtraction instead of addition. It also has to answer a different question than Two Sum, how many subarrays sum to k, not just whether one does. So the map holds how many times each prefix sum has occurred, not just whether it has, and instead of returning on the first match, we add that count to a running total and keep going.

One more detail, seed the map with {0: 1} before the loop starts. Without it, a subarray that sums to k starting right at index 0 has no earlier prefix sum to pair against, since there’s nothing before index 0. Seeding a prefix sum of 0 occurring once covers that case, “the sum of nothing before the array starts” is a valid starting point for a subarray.

// Subarray Sum Equals K
// https://leetcode.com/problems/subarray-sum-equals-k/description/
//
// Problem: given an array of integers and an integer k, return the
// number of contiguous subarrays whose elements sum to k.
//
// Track a running prefix sum, y, as we walk the array. The subarray
// between some earlier point x and here sums to y - x. We want that
// to equal k, so y - x = k, which means x = y - k. So at each step,
// the earlier prefix sum we need is y - k, and we check whether it
// already exists.
//
// This has to count how many subarrays sum to k, not just whether
// one does, so the map holds how many times each prefix sum has
// occurred, not just whether it occurred. Seed the map with
// { 0: 1 } before starting, so a subarray that sums to k starting
// right at index 0 still has a prefix sum of 0 to pair against.

function subarraySum(nums, k) {
    const prefixSumCounts = new Map();
    prefixSumCounts.set(0, 1);

    let runningSum = 0;
    let count = 0;

    for (const n of nums) {
        runningSum += n;

        const needed = runningSum - k;
        if (prefixSumCounts.has(needed)) {
            count += prefixSumCounts.get(needed);
        }

        prefixSumCounts.set(runningSum, (prefixSumCounts.get(runningSum) || 0) + 1);
    }

    return count;
}

module.exports = { subarraySum };

Grouping

Group Anagrams gives an array of strings and asks to group every string together with the other strings that are anagrams of it. Take ["eat", "tea", "tan", "ate", "nat", "bat"], the answer groups "eat", "tea", "ate" together, "tan", "nat" together, and leaves "bat" on its own.

The brute force compares every string against every other string to check if the two are anagrams, which is a pairwise check repeated over every pair, well past the point of being O(n) in the number of strings.

Two strings are anagrams exactly when they hold the same letters the same number of times each, so instead of comparing strings to each other, we can compute something from each string on its own that comes out identical for every member of the same group. Count the occurrences of each letter in a string, "eat" has one a, one e, one t. "tea" has the exact same counts, one a, one e, one t. "tan" has one a, one n, one t, a different set of counts entirely.

That per-letter count is what becomes the map key. Since strings only ever contain lowercase English letters, build a list of 26 numbers for each string, one slot per letter of the alphabet, each slot counting how many times that letter shows up. For "eat" and "tea", that list comes out identical, a 1 in the a slot, a 1 in the e slot, a 1 in the t slot, 0 everywhere else, which as an actual joined string is "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0". For "tan", the list is different, 1s in the a, n, and t slots, and a 0 in the e slot where "eat" had a 1, joining to "1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0", a different string entirely.

A list of numbers can’t be used as a map key directly, JavaScript doesn’t treat two separate arrays with matching contents as equal. So the list gets turned into a single string first, joining its 26 numbers together with commas. Two strings with matching letter counts now produce that exact same joined string, and that string is the key.

Walking the example: "eat" computes its key, the map has nothing under it yet, so a new bucket is created holding ["eat"]. "tea" computes the exact same key, since it has the same letters, finds that bucket already there, and gets appended, ["eat", "tea"]. "tan" computes a different key entirely, gets its own new bucket, ["tan"]. By the end, every bucket in the map is one finished group, built without ever comparing any string directly to another, only comparing each string’s own computed key against the map.

Computing the key this way costs O(k) per string of length k, one pass to build the count array. Sorting the string’s characters would also produce a valid key, "eat" and "tea" both sort to "aet", but sorting costs O(k log k), so the count array gets to the same answer without paying for a sort.

// Group Anagrams
// https://leetcode.com/problems/group-anagrams/description/
//
// Problem: given an array of strings, group the anagrams together.
// Strings consist of lowercase English letters.
//
// Two strings are anagrams exactly when they have the same letters,
// the same number of times each, so a per-letter count is a key
// that's identical for every string in the same group. Compute that
// key once per string, an O(k) pass over its letters, and bucket by
// it, rather than comparing strings to each other pairwise.

function groupAnagrams(strs) {
    const groups = new Map();

    for (const s of strs) {
        const counts = new Array(26).fill(0);
        for (const ch of s) {
            counts[ch.charCodeAt(0) - "a".charCodeAt(0)]++;
        }

        // Two anagrams produce the exact same 26-count array, so
        // joining it into a string gives a key that's identical for
        // every member of the same group.
        const key = counts.join(",");

        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(s);
    }

    return [...groups.values()];
}

module.exports = { groupAnagrams };

Valid Sudoku gives a 9x9 board, partially filled in, and asks whether the filled cells break any Sudoku rule, no repeated digit in the same row, column, or 3x3 box. Only the filled cells need checking, an empty cell contributes nothing to the check, and the board doesn’t need to be solvable or complete, just not already broken by what’s there. This is a different problem from Sudoku Solver, which fills in the empty cells by search, nothing here searches or guesses anything, just pointing out is the sudoku given is valid as of now.

Every number on the board sits at a position, (i, j), and that position resolves outward to three coordinates at once, which row it’s in, which column, and which box. Say a 5 sits at (2, 3). Row and column are handed to us directly, row 2, column 3. The box takes a small computation, a 9x9 grid is really a 3x3 grid of boxes, so Math.floor(2 / 3) = 0 gives the box-row, Math.floor(3 / 3) = 1 gives the box-column, and flattening that pair into a single index the way any 2D grid flattens into 1D gives 0 * 3 + 1 = 1. So (2, 3) resolves to row 2, column 3, box 1.

That mapping also runs in reverse, and the reverse direction is the part that actually does the work. Once (2, 3) resolves to row 2, column 3, box 1, the meaning of that 5 being there is that row 2 now contains a 5, column 3 now contains a 5, and box 1 now contains a 5. Each of those three facts gets recorded by adding 5 to that group’s set, row 2’s set, column 3’s set, and box 1’s set.

That reverse mapping is exactly what makes the duplicate check possible. In total there are 9 rows, 9 columns, and 9 boxes, 27 groups, one set each, 27 sets. Before adding a digit to its three sets, check whether it’s already sitting in any of them. If row 2’s set already contains a 5 when a second 5 shows up in row 2, the board is invalid right there. If not, add the digit to all three sets and move to the next cell.

// Valid Sudoku
// https://leetcode.com/problems/valid-sudoku/description/
//
// Problem: given a 9x9 Sudoku board, partially filled, determine if
// the filled cells satisfy the rules, no repeated digit in any row,
// column, or 3x3 box. Only filled cells need checking, empty cells
// ('.') are skipped entirely, the board doesn't need to be
// completable or solved, just not already broken.
//
// Every cell belongs to three groups at once, its row, its column,
// and its box. Keep one set per group, 9 rows + 9 columns + 9 boxes,
// and for each filled cell check its digit against all three of its
// groups before adding it to all three.

function boxIndex(row, col) {
    // A 9x9 grid is a 3x3 grid of boxes. Flooring row and col to
    // their box-row and box-col, then flattening that pair into a
    // single index the way any 2D grid flattens into 1D.
    return Math.floor(row / 3) * 3 + Math.floor(col / 3);
}

function isValidSudoku(board) {
    const rows = Array.from({ length: 9 }, () => new Set());
    const cols = Array.from({ length: 9 }, () => new Set());
    const boxes = Array.from({ length: 9 }, () => new Set());

    for (let r = 0; r < 9; r++) {
        for (let c = 0; c < 9; c++) {
            const digit = board[r][c];
            if (digit === ".") continue;

            const b = boxIndex(r, c);

            if (rows[r].has(digit) || cols[c].has(digit) || boxes[b].has(digit)) {
                return false;
            }

            rows[r].add(digit);
            cols[c].add(digit);
            boxes[b].add(digit);
        }
    }

    return true;
}

module.exports = { isValidSudoku };

Group Shifted Strings defines a shift operation, move every letter of a string forward one position in the alphabet, wrapping z back to a, so "abc" shifts to "bcd". Given an array of strings, group together any strings that can reach each other through some number of shifts. Strings of length 1 are all one group together, whatever letter they hold, that part is stated directly in the problem.

Take ["acd", "dfg", "wyz", "yab", "mop", "bdfh", "a", "x", "moqs"].

Shifting every letter by the same amount moves the whole string forward, but it never changes the gap between one letter and the next inside that string, only where the letters sit in the alphabet overall. "acd" has gaps 2, 1 (c is 2 past a, d is 1 past c). "dfg" has the exact same gaps, 2, 1. Both share a key before any shifting logic even needs to run.

Checking the rest of the list against that same 2, 1 key: "wyz" gives 2, 1. "yab" gives 2, 1 too, but only once the wraparound is handled, a is 2 past y going forward cyclically (y -> z -> a), and b is 1 past a. "mop" gives 2, 1 as well. All five, "acd", "dfg", "wyz", "yab", "mop", land in the same group.

"bdfh" has gaps 2, 2, 2, and "moqs" has gaps 2, 2, 2 too, a different group from the first five, and a different length besides. "a" and "x" are both length 1, no consecutive pair of letters to take a gap from at all, so both produce an empty gap sequence, the same key, which is exactly why length-1 strings all group together regardless of which letter they are.

// Group Shifted Strings
// https://www.geeksforgeeks.org/dsa/group-shifted-string/1
//
// Problem: shifting a string moves every letter to the next one
// cyclically, "abc" shifts to "bcd", "xyz" shifts to "yza". Group
// the given strings so that strings reachable from each other by
// some number of shifts land in the same group. Strings of length 1
// are all considered part of the same group, whatever letter they
// hold.
//
// Shifting every letter by the same amount never changes the gap
// between consecutive letters, only where they sit in the alphabet.
// So the sequence of gaps between consecutive letters, wrapping
// around from z to a, is identical for every string in the same
// shift group, and different for strings that aren't shift-related.
// That sequence of gaps is the key.

function shiftKey(s) {
    const gaps = [];
    for (let i = 1; i < s.length; i++) {
        const gap = (s.charCodeAt(i) - s.charCodeAt(i - 1) + 26) % 26;
        gaps.push(gap);
    }
    // A length-1 string has no consecutive pair at all, so its gap
    // list is empty, and every length-1 string shares that same
    // empty key, which is exactly the rule the problem states.
    return gaps.join(",");
}

function groupStrings(strings) {
    const groups = new Map();

    for (const s of strings) {
        const key = shiftKey(s);
        if (!groups.has(key)) groups.set(key, []);
        groups.get(key).push(s);
    }

    return [...groups.values()];
}

module.exports = { groupStrings };

Find Players With Zero or One Losses gives a list of [winner, loser] match results and asks for two sorted lists, every player who never lost, and every player who lost exactly once.

Every group so far in this bucket has used a computed string as the key, a sorted string, a count array, a sequence of gaps. Here the key is just a number, how many losses a player has, and the two lists the problem wants are simply two of the resulting groups, the group sitting under key 0 and the group sitting under key 1.

Take matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]. Walk every match and update a loss count per player, incrementing the loser’s count on every match. 3 loses to 1 and to 2, ending at 2 losses. 6 loses to 3 and to 5, 2 losses. 9 loses to 4 and to 10, 2 losses. 7, 5, 8, 4 each lose exactly once. 1, 2, 10 never appear as a loser anywhere in the list, 0 losses.

One detail the loop has to get right, a winner needs an entry in the map even before they’ve lost anything, otherwise a player who only ever wins never shows up in the 0 group at all. So the first time a player appears as a winner, record them with 0 losses, but only if they aren’t already in the map, a player who lost earlier and later wins a match keeps whatever loss count they already had.

Once every player has a loss count, group them by it, same shape as every other grouping problem, a map from key to the list of players sharing that key. Read off the group under 0, [1, 2, 10], and the group under 1, [4, 5, 7, 8], sort each for the required output format, and those are the two lists the problem asks for.

// Find Players With Zero or One Losses
// https://leetcode.com/problems/find-players-with-zero-or-one-losses/description/
//
// Problem: given a list of [winner, loser] match results, return two
// sorted lists, players who never lost a match, and players who lost
// exactly one match.
//
// The key here isn't computed from a string, it's a plain count, how
// many losses a player has. Group every player by that count, and
// the two lists the problem wants are just two specific groups out
// of however many exist, the group for count 0 and the group for
// count 1.

function findWinners(matches) {
    const lossCount = new Map();

    for (const [winner, loser] of matches) {
        // A winner needs to exist in the map with 0 losses if we
        // haven't seen them yet, but a winner who already has a
        // loss on record from an earlier match must keep that count.
        if (!lossCount.has(winner)) {
            lossCount.set(winner, 0);
        }
        lossCount.set(loser, (lossCount.get(loser) || 0) + 1);
    }

    const groupsByLossCount = new Map();
    for (const [player, losses] of lossCount) {
        if (!groupsByLossCount.has(losses)) groupsByLossCount.set(losses, []);
        groupsByLossCount.get(losses).push(player);
    }

    const zeroLosses = (groupsByLossCount.get(0) || []).sort((a, b) => a - b);
    const oneLoss = (groupsByLossCount.get(1) || []).sort((a, b) => a - b);

    return [zeroLosses, oneLoss];
}

module.exports = { findWinners };

Two Pointers: Asking the Right Questions

Seeing it in a statement

Every problem statement has two parts. What it asks for, the shape of the answer. What it offers, the structure in the input we can lean on. The pattern is where the two meet.

If moving a pointer means undoing something tracked over the whole range, it is not two pointers. Check Sliding Window.

Five problems follow, each read from its statement to the pattern. No code here, the code lives in Implementation and Examples.

1. 3Sum Closest

The statement. 3Sum Closest gives an array and a target, and asks for the sum of three elements that is closest to the target.

Asks for. The sum of three elements closest to a target.

Offers. An array we are free to sort, since only the sum is returned, not indices. Sorted array plus a target sum is the two-ends shape.

Why it fits. Fix one element, then place one pointer just after it and one at the far end. If the three values sum to less than the target, moving the left pointer right is the only move that can bring the sum up toward the target, and moving the right pointer left could only push it further away. If the sum is more than the target, the reverse holds. Each move is the only one that could get closer, so no better triple is ever skipped. Hashing does not fit here, since “closest” has no exact partner to look up.

2. Valid Palindrome II

The statement. Valid Palindrome II gives a string and asks whether it can be a palindrome after deleting at most one character.

Asks for. Whether the string can be a palindrome after one deletion.

Offers. A string with fixed first and last characters. Palindrome means comparing from both ends inward.

Why it fits. Start a pointer at each end. While the two characters match, both move inward, and this is safe because any palindrome needs that outer pair to match anyway. At the first mismatch, one of the two characters has to be the one deleted, since no deletion further inside can fix the outer pair. That leaves two options, skip the left character or skip the right one, and each option is a plain palindrome check on what remains. The single mismatch narrows the whole problem to two checks.

3. Merge Sorted Array

The statement. Merge Sorted Array gives two sorted arrays, where the first has empty space at its end equal to the length of the second, and asks for the second merged into the first in place, sorted.

Asks for. Two arrays merged in sorted order, in place.

Offers. Two sorted arrays and empty space at the end of the first. One pointer per array, filling from the back.

Why it fits. Filling from the front overwrites values of the first array that have not been read yet. Filling from the back does not. The largest value still unplaced is the larger of the two arrays’ last unread values, since both are sorted, and it belongs in the last empty slot. That slot is either free space or a position whose value has already been moved, so nothing unread gets overwritten. A third pointer marks where the next value goes, and it always stays behind the values still waiting to be read.

4. Is Subsequence

The statement. Is Subsequence gives two strings, s and t, and asks whether the characters of s appear in t in the same order, not necessarily next to each other.

Asks for. Whether s appears inside t in the same order.

Offers. Two sequences read left to right. One pointer per sequence, both moving forward.

Why it fits. The pointer in t moves forward every step. The pointer in s moves forward only when the two characters match. Matching a character of s at the earliest place it appears in t is always safe, since it leaves as much of t as possible for the characters that come after. If the pointer in s reaches its end, the answer is yes. A window does not fit, because the matched characters of t do not have to be next to each other and nothing gets undone when a pointer moves.

5. Find the Duplicate Number

The statement. Find the Duplicate Number gives n + 1 numbers, each between 1 and n, with exactly one value repeated. It asks for the repeated value without changing the array and using only a fixed amount of extra space.

Asks for. The repeated value, without changing the array or using extra space that grows with it.

Offers. Values that are all valid indices into the array. A set or a sort is ruled out, but following each value as a link turns the array into a linked list with a cycle.

Why it fits. Read each value as a pointer to the index it names, so index i leads to index nums[i]. Starting from index 0 and following these links, the walk can never leave the array, so it must eventually loop. No value is 0, so no link leads back to index 0, and the walk enters the loop from outside it. The index where it enters has two links leading into it, one from the path and one from inside the loop. Two links into one index means two positions hold the same value, so the index where the loop begins is the duplicate value itself. The problem has turned into a linked list with a cycle, and the fast and slow pointers find a cycle’s starting point without any extra structure.

What the five share

Every one has an order that position can lean on, a sorted array, the two ends of a string, two sequences read in order, or links that form a list. In every one, the pointer that moves is the one whose move can be argued safe in a single sentence, and no move ever needs to be undone. When something tracked across the whole range has to be corrected as a pointer moves, the problem belongs to Sliding Window. When the input has no usable order and the question is about values alone, it belongs to Hashing.

Implementation

Two pointers is two variables walking through the same data at once, each with its own rule for moving, and the two positions compared or combined to decide what happens next. On an array or string they are two indices.

let left = 0;
let right = nums.length - 1;

On a linked list there are no indices, so the two pointers are two variables holding node references.

let slow = head;
let fast = head;

No new data structure is involved either way. The pattern lives in how the two variables move relative to each other. Once a problem is recognized as one of the three shapes from Asking the Right Questions, the code follows a fixed form. These are the three skeletons, worth knowing from memory rather than re-derived each time.

Converging

function converging(sortedNums, target) {
    let left = 0;
    let right = sortedNums.length - 1;

    while (left < right) {
        const sum = sortedNums[left] + sortedNums[right];

        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }

    return [];
}

left < right is what stops the loop the moment the two pointers would cross or meet, past that point there’s no unchecked pair left between them. Exactly one of the two pointers moves on any given step, never both, since moving one is the entire safety argument, moving both at once would throw away the guarantee that comes from checking the comparison first.

Fast and Slow (compaction)

function fastSlow(nums, shouldKeep) {
    let slow = 0;

    for (let fast = 0; fast < nums.length; fast++) {
        if (shouldKeep(nums[fast], nums, slow)) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    return slow; // new length of the kept region
}

fast always advances, one pass over every element, no exceptions. slow only advances when the current element is worth keeping, so it always sits at the next open slot to write into. shouldKeep is whatever the problem defines as worth keeping, not equal to the previous kept value for Remove Duplicates, not zero for Move Zeroes.

Not every compaction problem fits two categories, though. Sort Colors needs three, everything before low confirmed one value, everything after high confirmed another, mid still scanning in between:

function threeWayPartition(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, the swapped-in value from high
            // hasn't been classified yet.
        }
    }
}

Linked List

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;
}

fast moves two nodes for every one slow moves, closing the gap between them by one node every step if a cycle exists, which is what guarantees they eventually land on the same node rather than just passing each other. The fast && fast.next check has to happen before advancing fast two steps, without it, fast.next.next would throw the moment fast runs off the end of a list with no cycle.

Two more shapes on linked lists don’t reduce to a single skeleton, they’re combinations of what’s already here. Finding the kth node from the end keeps a fixed gap between two pointers, k - 1 steps apart, then slides both forward together until the front one runs out, the same relative-position idea as fast and slow, just with a fixed offset instead of a fixed speed ratio. Reorder List and similar problems chain multiple phases together, find the middle with fast and slow, reverse a portion with a plain pointer-reversal loop, then merge two pointers walking in lockstep, three small, separately understood pieces run one after another rather than one clever loop doing everything at once.

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 };

Sliding Window: Asking the Right Questions

Seeing it in a statement

Every problem statement has two parts. What it asks for, the shape of the answer. What it offers, the structure in the input we can lean on. The pattern is where the two meet.

If a sum can go down when an element is added, negative numbers allowed, it is not sliding window. Check Hashing with prefix sums.

Five problems follow, each read from its statement to the pattern. No code here, the code lives in Implementation and Examples.

1. Find All Anagrams in a String

The statement. Find All Anagrams in a String gives two strings, s and p, and asks for every starting index in s where an anagram of p begins.

Asks for. Every start index where a substring of s is an anagram of p.

Offers. Substrings, and a size handed over, since an anagram of p has p’s length. Fixed size window.

Why it fits. Every stretch of s with p’s length is a candidate, and each one is checked by comparing letter counts with p, a Frequency question from hashing. Sliding forward by one changes exactly two letters, one leaves and one enters, so the counts are adjusted rather than rebuilt. The left edge moves whenever the stretch grows past p’s length. Hashing decides what a match is, the window decides how every position gets checked.

2. Fruit Into Baskets

The statement. Fruit Into Baskets describes a row of trees, each with one type of fruit, and two baskets that each hold one type. Starting at any tree and moving right, one fruit is picked from every tree, stopping at the first tree whose fruit fits in neither basket. It asks for the most fruit that can be picked.

Asks for. The most fruit that can be picked.

Offers. A story that hides a stretch. “Start at any tree, move right, stop” is a contiguous run, and “two baskets, one type each” is at most two distinct values. Stripped of the story, it is the longest subarray with at most two distinct values.

Why it fits. Adding a tree can only keep or raise the number of distinct types, and dropping the leftmost tree can only keep or lower it, so the direction holds. This is the maximizing form, the right edge always advances, and the left edge moves only while the run holds three types, with a count map tracking how many of each type are inside.

3. Minimum Window Substring

The statement. Minimum Window Substring gives two strings, s and t, and asks for the shortest substring of s that contains every character of t, duplicates included.

Asks for. The shortest substring that contains every character of t.

Offers. Substrings, and a threshold to reach. Shortest plus a threshold is the minimizing window.

Why it fits. Adding a character to the stretch can only cover more of t, and removing one can only cover less, so the direction holds. The right edge advances until the stretch covers all of t. Then the left edge moves while the stretch still covers it, and each of those steps is a chance at something shorter. A count of how many of t’s characters are fully covered makes “is it still valid” a single comparison.

4. Subarray Product Less Than K

The statement. Subarray Product Less Than K gives an array of positive integers and a number k, and asks how many contiguous subarrays have a product less than k.

Asks for. A count of contiguous subarrays whose product is below k.

Offers. Contiguous subarrays and positive values. The count looks unlike the other forms at first, and the word that settles it is “positive”.

Why it fits. Every value is at least 1, so multiplying in a new value can never shrink the product, and dividing out the leftmost value can never grow it. That is the direction check, and it passes. For each right edge, the left edge moves until the product drops below k. At that point every stretch that ends at the right edge and starts anywhere from the left edge onward is valid too, since removing values from the left of a valid stretch only lowers its product, so all of them are counted at once.

The same problem with negative numbers or zeros allowed fails the check, since a product could flip sign or collapse to zero as the stretch grows. Subarray Sum Equals K fails it for the same reason, and goes to Hashing.

5. Minimum Operations to Reduce X to Zero

The statement. Minimum Operations to Reduce X to Zero gives an array of positive integers and a number x. Each operation removes the leftmost or rightmost element and subtracts it from x. It asks for the fewest operations that bring x to exactly 0, or -1 if it cannot be done.

Asks for. The fewest elements removed from the two ends to reach a total of x.

Offers. A row with two open ends. The removed elements are never contiguous, but what stays behind is one unbroken block in the middle. The wording cue is “leftmost or rightmost”.

Why it fits. The removed elements sum to x, so the block left behind sums to the total minus x. Fewest operations means removing as few elements as possible, which means the longest block in the middle with that exact sum. All values are positive, so the direction holds. This is the maximizing form, with the left edge moving while the block’s sum is too big. A pointer at each end taking the larger value, which two pointers would suggest, has no safety argument here, since a small value at an edge can hide exactly the value needed behind it.

What the five share

Every one is about a contiguous stretch, written in the statement, hidden in a story, or hidden in what is left behind. In every one, adding an element moves the tracked value one way and removing one moves it back, and the problem stops at that check whenever negative numbers or zeros could break it. Once both hold, the remaining question is what moves the left edge, a given size, an invalid stretch, or a stretch that is still valid. When moving a pointer undoes nothing, the problem belongs to Two Pointers instead.

Implementation

A sliding window is two indices, left and right, plus a variable holding whatever is being tracked about the range between them.

let left = 0;
let right = 0;
let windowSum = 0;

The tracked value depends on the problem, a plain number for a sum, a Set for distinct characters, a Map for character counts. There is no special type involved. The pattern lives in how left and right move relative to each other and how the tracked value is adjusted as they do.

One loop underlies every sliding window problem. right always advances, one step per iteration, no exceptions. left advances under a condition, checked every step. The only thing that changes between problems is where that condition comes from.

Fixed size

The condition is handed over directly by the problem, the window’s length can’t exceed k. Build the aggregate over the first k elements once, then slide, adding the incoming element and removing the departing one at the same time.

function fixedWindow(nums, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    let best = windowSum;

    for (let right = k; right < nums.length; right++) {
        windowSum += nums[right] - nums[right - k];
        best = Math.max(best, windowSum);
    }

    return best;
}

right - k is always the element leaving the window the moment right enters it, the fixed width guarantees that pairing, no separate check needed to know what to remove.

Variable size, maximizing under a limit

No condition is handed over here, it has to come from whatever makes the window invalid, too many distinct characters, a repeated character, some tracked value crossing a limit. Shrink left only while the window is currently invalid, stop the moment it becomes valid again, and only update the answer once it’s valid.

function maximizeWindow(nums, isValid) {
    let left = 0;
    let best = 0;

    for (let right = 0; right < nums.length; right++) {
        addToWindow(nums[right]);

        while (!isValid()) {
            removeFromWindow(nums[left]);
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

Variable size, minimizing to meet a threshold

Same missing-condition problem, opposite direction. Shrink left while the window is still currently valid, recording the answer at every point along the way, since each shrink is a chance at something smaller. Stop shrinking the moment it becomes invalid.

function minimizeWindow(nums, meetsThreshold) {
    let left = 0;
    let best = Infinity;

    for (let right = 0; right < nums.length; right++) {
        addToWindow(nums[right]);

        while (meetsThreshold()) {
            best = Math.min(best, right - left + 1);
            removeFromWindow(nums[left]);
            left++;
        }
    }

    return best === Infinity ? 0 : best;
}

The direction of the while condition is what separates this from maximizing, !isValid() shrinks to escape a bad state, meetsThreshold() shrinks to keep testing a good one. Mixing the two up is the most common way this pattern breaks, shrinking on the wrong condition either stops too early or never stops at all.

The one question that actually matters

right always advances, that never changes. The aggregate updating incrementally is mechanical once it’s clear what to track. The one piece of real thinking left, every single time, is answering “what moves left forward.”

Fixed size answers it directly, the window’s size exceeding k. Maximizing answers it as “the window just became invalid.” Minimizing answers it as “the window is still valid, keep pushing to see how much smaller it gets.” Three different sources for the exact same question, and once that question has an answer for a given problem, the rest of the code is close to boilerplate.

That holds for hidden windows too, once the window has been found. In Maximum Points You Can Obtain from Cards the window is the cards left behind, fixed at n - k, so the fixed-size skeleton applies with a minimum in place of a maximum. In Frequency of the Most Frequent Element the window is a stretch of the sorted array, and the maximizing skeleton applies with a cost within a budget as the validity check. Finding the window is the extra work, and the loop itself does not change.

Sliding Window: Examples

Worked problems from the questions chapter, reasoning and code together, one shape at a time.

Fixed Size

Maximum Average Subarray I gives an array and an integer k, and asks for the contiguous subarray of length k with the highest average, returning that average. The size is handed over directly, which makes this the cleanest place to see the mechanics with nothing else in the way.

Brute force computes the sum of every window of size k from scratch, adding up k elements each time, O(n * k) overall. But two neighboring windows share k - 1 elements, sliding forward by one only changes two of them, one leaves from the left, one enters from the right. The sum doesn’t need rebuilding, only adjusting by the difference between those two.

The one question this whole pattern comes down to, what moves left forward, has the simplest possible answer here. Nothing about the window’s contents matters, only its length, once the window would grow past k, the oldest element has to leave. The code never even tracks left explicitly, right - k is always the element about to leave.

Take nums = [1, 12, -5, -6, 50, 3], k = 4. The first window, [1, 12, -5, -6], sums to 2.

right  enters  leaves  windowSum  bestSum
4      50      1       51         51
5      3       12      42         51

bestSum ends at 51, from the window [12, -5, -6, 50], and 51 / 4 = 12.75, the answer.

This array has negative numbers, and nothing breaks. The direction check from Question 3, whether growing the window always moves the tracked value the same way, only matters when the shrinking condition is derived from the window’s contents. Here the condition is just size, so it never comes up.

// Maximum Average Subarray I
// https://leetcode.com/problems/maximum-average-subarray-i/description/
//
// Problem: given an array and an integer k, find the contiguous
// subarray of length k with the highest average, and return that
// average.
//
// The window's size is given directly, so what moves left forward
// is just the window's length reaching past k, nothing about its
// contents. Build the sum of the first k elements once, then slide,
// adding the element entering and subtracting the one leaving.

function findMaxAverage(nums, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    let bestSum = windowSum;

    for (let right = k; right < nums.length; right++) {
        // nums[right] enters, nums[right - k] leaves, the window
        // stays exactly k wide without any separate size check.
        windowSum += nums[right] - nums[right - k];
        bestSum = Math.max(bestSum, windowSum);
    }

    return bestSum / k;
}

module.exports = { findMaxAverage };

Permutation in String gives two strings, s1 and s2, and asks whether s2 contains a permutation of s1 as a contiguous substring.

Read the statement the same way as before, and notice what’s missing. There’s no min or max ask, the answer is a yes or no. But “substring” is still the contiguous range, and the window’s size is handed over directly, a permutation of s1 has exactly s1’s length. So this is the fixed-size shape, and the answer to “what moves left” is the same as in Maximum Average Subarray, the window’s length reaching past s1’s length.

A permutation of s1 is an anagram of s1, same letters, same counts. That’s the Valid Anagram question from the Hashing chapter, asked of every window of s2 that is exactly s1’s length. Checking each window from scratch would rebuild its letter counts every time. Sliding window supplies the other half of the solution, moving the window forward changes exactly two letters, one leaves, one enters, so the counts adjust in constant time. Hashing decides what a match means, sliding window decides how to check it at every position without redoing the work.

Comparing the two count arrays in full after every move would cost a scan of 26 letters each time. The same idea from Minimum Window Substring applies here, keep a counter, matches, of how many of the 26 letters currently have equal counts in both. A letter becomes matched when its count reaches the target, and stops being matched when it moves one past it. The window is a permutation exactly when matches reaches 26.

Take s1 = "ab", s2 = "eidbaooo", so the window is 2 wide. The first window, ei, has 22 letters matching, every letter except a, b, e, and i.

right  window  entering  leaving  matches
2      id      d         e        22
3      db      b         i        24
4      ba      a         d        26

At right = 2, d enters and stops matching, e leaves and starts matching again, so matches holds at 22. At right = 3, b enters and reaches its target, i leaves and starts matching, matches goes to 24. At right = 4, a enters and reaches its target, d leaves and starts matching, matches reaches 26, and the answer is true, the window ba is a permutation of ab.

// Permutation in String
// https://leetcode.com/problems/permutation-in-string/description/
//
// Problem: given two strings of lowercase letters, s1 and s2,
// return true if s2 contains a permutation of s1 as a contiguous
// substring.
//
// A permutation of s1 is an anagram of s1, same letters, same
// counts. That's the Valid Anagram question from the Hashing
// chapter, asked of every window of s2 that is exactly s1's length.
// Sliding window supplies the other half, sliding forward changes
// only two letters, so the counts adjust in constant time instead
// of being rebuilt for every window.
//
// Instead of comparing the two count arrays in full every step,
// keep a counter, matches, of how many of the 26 letters currently
// have equal counts in both. The window is a permutation exactly
// when matches reaches 26.

function checkInclusion(s1, s2) {
    const k = s1.length;
    if (k > s2.length) return false;

    const index = (ch) => ch.charCodeAt(0) - "a".charCodeAt(0);
    const need = new Array(26).fill(0);
    const window = new Array(26).fill(0);

    for (let i = 0; i < k; i++) {
        need[index(s1[i])]++;
        window[index(s2[i])]++;
    }

    let matches = 0;
    for (let i = 0; i < 26; i++) {
        if (need[i] === window[i]) matches++;
    }
    if (matches === 26) return true;

    for (let right = k; right < s2.length; right++) {
        const entering = index(s2[right]);
        const leaving = index(s2[right - k]);

        // Update matches after each change, a letter becomes matched
        // when its count reaches the need, and stops being matched
        // when it moves one past the need.
        window[entering]++;
        if (window[entering] === need[entering]) matches++;
        else if (window[entering] === need[entering] + 1) matches--;

        window[leaving]--;
        if (window[leaving] === need[leaving]) matches++;
        else if (window[leaving] === need[leaving] - 1) matches--;

        if (matches === 26) return true;
    }

    return false;
}

module.exports = { checkInclusion };

Sliding Window Maximum gives an array and a window size k, and asks for an array containing the maximum of every window as it slides across, one number per window position. For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the answer is [3, 3, 5, 5, 6, 7].

The size is given, so this is the fixed-size shape, and left moves when the window’s length passes k. The maximum being asked for is the largest value inside each window, not a window size, so there’s no min or max ask over sizes here, same as Permutation in String.

The brute force finds the max of every window by scanning all k of its elements, n - k + 1 windows at k elements each, O(n * k). Each slide changes exactly two things, one element leaves, one enters, and the other k - 1 elements stay exactly as they were. The brute force ignores that and re-reads them anyway.

For a sum, using that is one line, add the entering number, subtract the leaving one. A maximum has no such shortcut. A single running max works until the max itself leaves the window, and then there’s nothing to subtract, the next biggest has to come from somewhere in the elements that stayed, and a lone variable never recorded it. So the question becomes: for the k - 1 elements that stay, what is the least that needs to be remembered so the next max can be answered without re-reading them?

Remembering only the max and the second max feels like enough, and it isn’t. Take nums = [9, 8, 7, 6, 5], k = 3, correct answers [9, 8, 7]. The first window [9, 8, 7] has max 9, second 8, and 7 gets thrown away. Slide, 9 leaves, 6 enters, the window is [8, 7, 6], the max is 8, correct, but the new second max should be 7, which was discarded, so 6 takes its place. Slide again, 8 leaves, the window is [7, 6, 5], and the tracker only knows 6, so it reports 6 when the true max is 7. In a decreasing run, every number in the window gets its turn as the max, one after another, as the bigger ones ahead of it leave, so every one of them has to be remembered.

What can be forgotten is a number that will never get a turn. A number that is both older and smaller than something that arrived after it. Take [3, 1, 2]. 1 sits before 2, so 1 leaves the window before 2 does, and 2 is bigger the whole time they share the window. 1 will never be the max, so it can be dropped. Smaller numbers that arrive later are the ones to keep, since they are still in the window after the bigger ones ahead of them leave.

That list of surviving candidates is kept in a deque, short for double-ended queue, a list where items can be added and removed at both ends. A regular queue only adds at the back and removes from the front, a stack only touches one end, a deque allows both, and this problem uses both.

A new number arrives, and everything smaller than or equal to it is removed from the back, one at a time, stopping at the first number that is bigger, then the new number is added at the back. The front number’s position has slid out of the window, so it is removed from the front. The current max is needed, so the front is read.

The deque ends up in decreasing order from front to back, but nothing sorts it. The order is a side effect of the removal rule, every number gets removed if something bigger and newer arrives behind it, so whatever sits in front of any number is bigger or equal. That’s why the front is always the max, and finding the max costs nothing, no scan. It also never holds the whole window, only the survivors, and can be shorter than the window, never longer. Numbers equal to the new one are removed too, the newer copy leaves later and is just as large, so the older one never matters.

If a new number is smaller than the front but bigger than the back, removal continues from the back until it reaches something bigger, and the new number goes right after it. With deque values [7, 5, 2] and a new number 4, 2 is removed, 5 is bigger so removal stops, and 4 is added, giving [7, 5, 4]. It sits in the middle of the old contents by value but at the back of the deque, since everything that was behind it was removed.

Take nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3, showing the deque’s values.

new number  deque after       max
1           [1]               -
3           [3]               -      (1 dropped, 3 beats it)
-1          [3, -1]           3
-3          [3, -1, -3]       3
5           [5]               5      (-3, -1, 3 all dropped)
3           [5, 3]            5
6           [6]               6      (3 and 5 dropped)
7           [7]               7

When 5 arrives, the window is [-1, -3, 5], but the deque holds only 5. -1 and -3 sit before 5 and leave sooner, so they can never win again. The result is [3, 3, 5, 5, 6, 7].

Nothing in that trace ever removed the front for sliding out of the window, because every number arriving was big enough to clear things first. That case shows up in a decreasing run. Take nums = [9, 8, 7, 6, 5], k = 3.

new number  deque before front check  front out of window?  deque after   max
9           [9]                       no                     [9]           -
8           [9, 8]                    no                     [9, 8]        -
7           [9, 8, 7]                 no                     [9, 8, 7]     9
6           [9, 8, 7, 6]              yes, 9 slid out        [8, 7, 6]     8
5           [8, 7, 6, 5]              yes, 8 slid out        [7, 6, 5]     7

Nothing new beats anything ahead of it, so the deque keeps everything, and the front leaves purely because its position slid out of the window. The result is [9, 8, 7], the correct answer, and the exact case where keeping only the max and the second max failed.

Each number is added to the deque once and removed at most once, so the whole thing runs in O(n), even though a single step can remove many numbers. The code stores indices instead of values, since the front’s position is what says whether it has slid out.

// Sliding Window Maximum
// https://leetcode.com/problems/sliding-window-maximum/description/
//
// Problem: given an array and a window size k, return an array where
// each entry is the maximum of one window as it slides across, so
// the result has one number per window position.
//
// The window's size is given, so this is the fixed-size shape. The
// difficulty is the tracked value. A maximum has no undo, when the
// current max leaves the window there is nothing to subtract, and
// the next biggest has to already be known.
//
// A deque of indices solves it. It holds only the numbers that could
// still become the max, in decreasing order of value, so the front
// is always the current max.
//
//   New number arrives: remove from the back while the back is
//   smaller than or equal to it, those are older and smaller, so
//   they leave the window first and can never win again. Then add
//   the new number at the back.
//
//   Front number has slid out of the window: remove it from the
//   front.
//
//   Max needed: read the front.
//
// JavaScript has no built-in deque. An array handles the back
// (push and pop are fast). For the front, a head index moves forward
// instead of calling shift(), which can be slow on large arrays.

function maxSlidingWindow(nums, k) {
    const deque = []; // indices into nums, values decreasing
    let head = 0; // deque[head] is the front
    const result = [];

    for (let right = 0; right < nums.length; right++) {
        // Drop everything at the back that the new number beats.
        while (deque.length > head && nums[deque[deque.length - 1]] <= nums[right]) {
            deque.pop();
        }
        deque.push(right);

        // The window covers right - k + 1 through right. If the
        // front's index is older than that, it has slid out.
        if (deque[head] <= right - k) {
            head++;
        }

        // Windows only exist once the first k numbers have arrived.
        if (right >= k - 1) {
            result.push(nums[deque[head]]);
        }
    }

    return result;
}

module.exports = { maxSlidingWindow };

Variable Size, Maximizing

Longest Substring Without Repeating Characters gives a string and asks for the length of the longest substring with no repeated character.

Read the problem statement word by word. “Longest” is a max ask, the first signal. “Substring” is a contiguous range, the second signal, stronger. “Without repeating characters” is the third, it hands over the condition that moves left, the window is invalid the moment a character shows up twice inside it. It also passes the direction check on its own, dropping a character off the left edge can only reduce or keep the same number of duplicates, never create a new one.

The brute force checks every substring for duplicates, rebuilding a set of its characters each time. The window keeps one set alive instead, holding exactly the characters currently inside it, added to as right grows, removed from as left shrinks. That removal is the undo step, and it’s what marks this as sliding window rather than plain two pointers.

Each time right reaches a new character, one question decides everything, is that character already inside the window. If not, add it and move on. If yes, left has to step forward, dropping characters off the left edge one at a time, until the duplicate is gone, and only then does the new character go in.

That check has to happen before adding, not after. A Set silently ignores an attempt to add a value it already holds, so adding first would hide the very duplicate we need to notice.

Take s = "abcabcbb".

right  char  window before  action                           left  window after  best
0      a     {}             add                              0     {a}           1
1      b     {a}            add                              0     {a, b}        2
2      c     {a, b}         add                              0     {a, b, c}     3
3      a     {a, b, c}      a inside, drop a, then add       1     {b, c, a}     3
4      b     {b, c, a}      b inside, drop b, then add       2     {c, a, b}     3
5      c     {c, a, b}      c inside, drop c, then add       3     {a, b, c}     3
6      b     {a, b, c}      b inside, drop a, drop b, add    5     {c, b}        3
7      b     {c, b}         b inside, drop c, drop b, add    7     {b}           3

best ends at 3, from the window abc, matching the known answer.

// Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
//
// Problem: given a string, return the length of the longest
// substring that contains no repeated character.
//
// "Longest" is the max ask, "substring" is the contiguous range,
// "without repeating" is the condition that moves left forward.
// The tracked value is a set of the characters currently inside
// the window, added to as right grows, removed from as left shrinks.

function lengthOfLongestSubstring(s) {
    const inWindow = new Set();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        // A Set can't hold a duplicate, so the check has to happen
        // before adding, not after. If the character entering is
        // already inside the window, shrink from the left until it
        // isn't.
        while (inWindow.has(s[right])) {
            inWindow.delete(s[left]);
            left++;
        }

        inWindow.add(s[right]);
        best = Math.max(best, right - left + 1);
    }

    return best;
}

module.exports = { lengthOfLongestSubstring };

Longest Repeating Character Replacement gives a string of uppercase letters and an integer k. Up to k characters can be replaced with any other letter, and the question is the length of the longest substring that can be made all one letter.

“Longest” is the max ask, “substring” is the contiguous range. The third piece, the condition that moves left, isn’t stated anywhere in the problem, it has to be derived. A window can be turned into all one letter by replacing every character that isn’t its most frequent letter, so the number of replacements needed is windowSize - countOfMostFrequentLetter. The window is valid while that stays at most k, and invalid the moment it goes over, which is when left steps forward.

The tracked value here is a frequency map of the letters currently inside the window, incremented as right adds a letter, decremented as left drops one. That’s the Frequency bucket from the Hashing chapter sitting inside the window. Sliding window decides how the window moves, hashing supplies what gets tracked inside it, and most non-trivial sliding window problems are one wrapped around the other.

Take s = "AABABBA", k = 1.

right  char  window after shrinking  counts     size  most  size - most  best
0      A     A                       A1         1     1     0            1
1      A     AA                      A2         2     2     0            2
2      B     AAB                     A2 B1      3     2     1            3
3      A     AABA                    A3 B1      4     3     1            4
4      B     BAB                     A1 B2      3     2     1            4
5      B     BABB                    A1 B3      4     3     1            4
6      A     BBA                     A1 B2      3     2     1            4

At right = 4 the window AABAB needs 5 - 3 = 2 replacements, over k = 1, so left steps forward twice, first dropping an A, then another A, until the window is BAB. The same thing happens at right = 6. best ends at 4, the known answer for this input.

A widely used version of this solution skips recomputing the most frequent count on every shrink, it keeps a running maximum that only ever goes up and never lowers it. That saves scanning the map each time and gives correct answers, but proving that a stale maximum can never inflate the result takes a subtler argument than belongs here. The version below recomputes exactly, which stays cheap since the map never holds more than 26 letters.

// Longest Repeating Character Replacement
// https://leetcode.com/problems/longest-repeating-character-replacement/description/
//
// Problem: given a string of uppercase letters and an integer k,
// you may replace up to k characters with any other letter. Return
// the length of the longest substring that can be made all one
// letter this way.
//
// "Longest" is the max ask, "substring" is the contiguous range.
// The condition that moves left isn't stated, it has to be derived.
// A window can be made all one letter if the characters that aren't
// its most frequent letter number at most k, those are the ones
// that get replaced. So the window is valid while
// windowSize - countOfMostFrequentLetter <= k.
//
// The tracked value is a frequency map of the letters currently in
// the window, incremented as right grows, decremented as left shrinks.

function characterReplacement(s, k) {
    const counts = new Map();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        counts.set(s[right], (counts.get(s[right]) || 0) + 1);

        // Recompute the most frequent letter's count from the map
        // each time. At most 26 entries, so this stays cheap.
        while (right - left + 1 - Math.max(...counts.values()) > k) {
            counts.set(s[left], counts.get(s[left]) - 1);
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

module.exports = { characterReplacement };

Variable Size, Minimizing

Minimum Size Subarray Sum gives an array of positive integers and a target, and asks for the length of the shortest contiguous subarray whose sum is at least the target, or 0 if no such subarray exists.

The problem guarantees every number is positive, no zeros, no negatives. That guarantee is what makes everything below work, and it’s worth holding onto from the start.

“Minimum” is the min ask, “subarray” is the contiguous range. The condition that moves left flips direction from the last two problems. Those shrank while the window was invalid. Here, growing right pushes the sum toward the target, so once the sum reaches it, the window is valid, and left keeps stepping forward for as long as the window stays valid, recording a smaller answer at every step, stopping only when dropping one more element would break it.

Because every number is positive, growing the window can only raise the sum and shrinking it can only lower it. That’s the direction check passing, and it’s the reason it’s safe to stop shrinking the moment the sum drops below the target, nothing further along could have brought it back up.

Take target = 7, nums = [2, 3, 1, 2, 4, 3].

right  added  sum  shrink steps                              left  sum after  best
0      2      2    none                                      0     2          -
1      3      5    none                                      0     5          -
2      1      6    none                                      0     6          -
3      2      8    record 4, drop 2                          1     6          4
4      4      10   record 4, drop 3, record 3, drop 1        3     6          3
5      3      9    record 3, drop 2, record 2, drop 4        5     3          2

best ends at 2, from the window [4, 3], the known answer for this input.

Now the same idea with a negative number, to see exactly what breaks. Take target = 5, nums = [4, -5, 6]. The true answer is 1, the single element [6]. Running the same loop, right = 2 gives a sum of 4 - 5 + 6 = 5, valid, record a length of 3. Then left drops the 4, the sum falls to 1, below the target, and the loop stops, reporting 3. It stopped too early. The element actually blocking a smaller answer was the -5 in the middle, and dropping it would have raised the sum, but the loop only shrinks while the sum stays at or above the target, so it never got that far. With negatives in the array, growing or shrinking the window no longer moves the sum in one predictable direction, and this shrinking condition stops being trustworthy. That’s the case Subarray Sum Equals K in the Hashing chapter handles with prefix sums instead.

// Minimum Size Subarray Sum
// https://leetcode.com/problems/minimum-size-subarray-sum/description/
//
// Problem: given an array of POSITIVE integers and a target, return
// the length of the shortest contiguous subarray whose sum is at
// least the target, or 0 if none exists.
//
// "Minimum" is the min ask, "subarray" is the contiguous range.
// The condition that moves left is the window's sum reaching the
// target. Once it does, the window is valid, and left keeps stepping
// forward for as long as it stays valid, recording a smaller answer
// at every step.
//
// This only works because every number is positive. Growing the
// window can only raise the sum, shrinking it can only lower it,
// so once dropping the leftmost element breaks the window, nothing
// further along could have helped.

function minSubArrayLen(target, nums) {
    let left = 0;
    let windowSum = 0;
    let best = Infinity;

    for (let right = 0; right < nums.length; right++) {
        windowSum += nums[right];

        while (windowSum >= target) {
            best = Math.min(best, right - left + 1);
            windowSum -= nums[left];
            left++;
        }
    }

    return best === Infinity ? 0 : best;
}

module.exports = { minSubArrayLen };

Minimum Window Substring gives two strings, s and t, and asks for the shortest substring of s that contains every character of t, duplicates included, or an empty string if none exists.

“Minimum” is the min ask, “substring” is the contiguous range. The condition that moves left is the window containing everything t needs, so the shape matches the last problem, right grows until the window becomes valid, then left shrinks for as long as it stays valid, recording the smallest window along the way.

What’s different is how validity works. The last problem checked a single running sum against a target. Here, validity is about how many of each specific character the window holds, which points to a frequency map, two of them, one for what t requires, built once, and one for what the window currently holds, adjusted as right grows and left shrinks. The direction check still holds, adding a character can never reduce what the window covers, and dropping one can never add coverage.

Comparing the two maps in full after every move would cost a scan each time. The usual trick keeps a single counter instead, formed, the number of distinct required characters that currently have enough copies in the window. It only changes at the exact moment a character’s count reaches its required amount going up, or drops below it going down. Extra copies beyond the requirement change nothing, and neither does dropping one of them. Validity becomes one comparison, formed against the number of distinct characters in t.

Take s = "ADOBECODEBANC", t = "ABC", so A, B, and C are each required once.

right  char  formed  events                                               left  best
0-2    A D O 1       none                                                 0     -
3      B     2       none                                                 0     -
4      E     2       none                                                 0     -
5      C     3       valid, record ADOBEC (6), drop A, formed back to 2    1     ADOBEC
6-8    O D E 2       none                                                 1     ADOBEC
9      B     2       B count is now 2, formed unchanged                    1     ADOBEC
10     A     3       valid, windows of 10, 9, 8, 7, 6 are none smaller,    6     ADOBEC
                     dropping C at left 5 sends formed back to 2
11     N     2       none                                                 6     ADOBEC
12     C     3       valid, 7 and 6 are not smaller, record EBANC (5),     10    BANC
                     record BANC (4), drop B, formed back to 2

At right = 9, the second B arrives and formed doesn’t move, B was already covered. Later, when left drops the first B, its count falls from 2 to 1, still enough, so formed doesn’t move then either. The answer is BANC, the known result for this input.

// Minimum Window Substring
// https://leetcode.com/problems/minimum-window-substring/description/
//
// Problem: given strings s and t, return the shortest substring of
// s that contains every character of t, duplicates included, or an
// empty string if no such substring exists.
//
// "Minimum" is the min ask, "substring" is the contiguous range.
// The condition that moves left is the window containing everything
// t needs. Two frequency maps are involved, what t requires (built
// once) and what the window currently holds (adjusted as right grows
// and left shrinks).
//
// Comparing the two maps in full after every move would cost a scan
// each time. Instead, keep a single counter, formed, of how many
// distinct required characters currently have enough copies in the
// window, and only touch it when a character's count crosses its
// required amount. Validity then becomes one comparison.

function minWindow(s, t) {
    if (t.length > s.length) return "";

    const need = new Map();
    for (const ch of t) {
        need.set(ch, (need.get(ch) || 0) + 1);
    }
    const required = need.size;

    const window = new Map();
    let formed = 0;
    let left = 0;
    let bestLength = Infinity;
    let bestStart = 0;

    for (let right = 0; right < s.length; right++) {
        const entering = s[right];
        window.set(entering, (window.get(entering) || 0) + 1);

        // Only the exact moment the count reaches the required
        // amount counts. Extra copies beyond that change nothing.
        if (need.has(entering) && window.get(entering) === need.get(entering)) {
            formed++;
        }

        while (formed === required) {
            if (right - left + 1 < bestLength) {
                bestLength = right - left + 1;
                bestStart = left;
            }

            const leaving = s[left];
            window.set(leaving, window.get(leaving) - 1);

            // Only dropping below the required amount breaks it.
            if (need.has(leaving) && window.get(leaving) < need.get(leaving)) {
                formed--;
            }
            left++;
        }
    }

    return bestLength === Infinity ? "" : s.substring(bestStart, bestStart + bestLength);
}

module.exports = { minWindow };

Twists on the Standard Shapes

The problems above each fit one of the three shapes as stated. The four below need one extra move before the window applies, a reframing, a subtraction, a sort, or a baseline. Three of them have a hidden window, one the statement never mentions, covered in Question 5 of Asking the Right Questions. Each one still comes down to the same question, what moves left, but the work is in getting the problem into a shape where that question has an answer.

Maximum Points You Can Obtain from Cards lays cards in a row, each with a point value. In each of k steps, take one card from either the left end or the right end, and the goal is the maximum total points.

Read the statement the way the earlier problems were read. “Maximum” is the max ask, the first signal. But the cards come off the two ends, so there is no contiguous range in what gets taken, and the second signal doesn’t fire on the surface. The window in this problem is hidden, and the steps below are how it comes out.

Only the first k and the last k cards matter. Exactly k cards get taken, so at most k of them come from the left, and nothing past the first k cards on the left can ever be reached. The same holds on the right. In [1, 2, 3, 4, 5, 6, 1] with k = 3, the reachable cards are 1, 2, 3 on the left and 5, 6, 1 on the right. The 4 in the middle can never be taken, whatever the choices are.

When k is more than half of n, the two ends overlap. The first k and the last k cards then share some cards, and every card is reachable, so nothing drops out of the problem. Nothing gets counted twice either. A choice takes i cards from the left and k - i from the right, those add up to exactly k, and k is at most n, so the two ends never reach the same card. At the extreme, k = n, every card is taken and the answer is the total.

Picking the bigger end each step fails. Each step only offers the leftmost or the rightmost card, which suggests two pointers, one at each end, taking whichever card is bigger. Take [1, 2, 100000, 3, 4, 5] with k = 3. Comparing the ends takes 5, then 4, then 3, for 12. The best answer is 1 + 2 + 100000 = 100003, taking three cards from the left. This fails the test from the Two Pointers chapter, a pointer is only safe to move when it can never lose a better answer, and here taking the bigger end can lose one, since a small card at the edge can sit directly in front of a huge one. The decision can’t be made one card at a time by looking at the two ends, it has to be made about the split as a whole, how many cards come from the left.

The cards left behind form a window. Take i cards from the left and k - i from the right, and what remains is exactly n - k cards in one unbroken block in the middle. Sliding that block from one end of the array to the other covers every split, from i = 0 to i = k. The points taken are the total minus the sum of that block, so taking the most points is the same as leaving the least. The window is hidden because it isn’t in the cards taken, it’s in the ones not taken. Its size is fixed at n - k, and what is being asked for is its smallest sum, so this is the fixed-size shape. The answer is the total of all cards minus the smallest window sum.

That settles the [1, 2, 100000, 3, 4, 5] case. The window is 6 - 3 = 3 wide and the total is 100015. The window sums are 100003, 100005, 100007, and 12. The smallest is 12, from the block [3, 4, 5], so the answer is 100015 - 12 = 100003, with no card-by-card choice made anywhere.

The cue to carry to other problems is the wording, “from either end” or “from the edges” is a hint to look at what sits in the middle, not at the ends.

Take cardPoints = [1, 2, 3, 4, 5, 6, 1], k = 3. The total is 22, and the window is 7 - 3 = 4 wide. The first window, [1, 2, 3, 4], sums to 10.

right  enters  leaves  windowSum  minWindow
4      5       1       14         10
5      6       2       18         10
6      1       3       16         10

The smallest window sum is 10, so the answer is 22 - 10 = 12, taking 5, 6, and 1 from the right end.

// Maximum Points You Can Obtain from Cards
// https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/description/
//
// Problem: cards lie in a row, each with a point value. In each of
// k steps, take one card from either the left end or the right end.
// Return the maximum total points obtainable.
//
// The cards taken are never a contiguous range, they come from the
// two ends. The cards left behind are. Taking i cards from the left
// and k - i from the right always leaves exactly n - k cards in a
// row in the middle, and every position of that middle block is
// reachable. So maximizing what is taken means minimizing what is
// left, the smallest sum of any window of size n - k.

function maxScore(cardPoints, k) {
    const n = cardPoints.length;
    const windowSize = n - k;

    let total = 0;
    for (const points of cardPoints) {
        total += points;
    }

    // Taking every card leaves an empty window.
    if (windowSize === 0) return total;

    let windowSum = 0;
    for (let i = 0; i < windowSize; i++) {
        windowSum += cardPoints[i];
    }
    let minWindow = windowSum;

    for (let right = windowSize; right < n; right++) {
        windowSum += cardPoints[right] - cardPoints[right - windowSize];
        minWindow = Math.min(minWindow, windowSum);
    }

    return total - minWindow;
}

module.exports = { maxScore };

Count Number of Nice Subarrays gives an array of positive integers and an integer k, and asks for the number of contiguous subarrays that contain exactly k odd numbers.

Read the statement the usual way. There’s no min or max ask, the answer is a count. “Subarray” is the contiguous range. So the recognition only half fires, and the third stage, the condition that moves left, is where it gets stuck. A window handles “at most k odd numbers” cleanly, adding an element can only keep or raise the odd count and dropping one from the left can only keep or lower it. “Exactly k” breaks that. A window with too few odd numbers and one with too many are both invalid, so no single direction of shrinking fixes both.

A first attempt, and what it misses. Grow right until the window holds k odd numbers, then walk left forward over the leading even numbers, adding one to a count at each step, since each step is another valid start. Take [2, 1, 1] with k = 2. At right = 2, the valid starts are index 0, giving [2, 1, 1], and index 1, giving [1, 1]. That’s two subarrays, not one. The leading 2 is an even number, so starting before it or after it gives the same odd count.

It still isn’t enough to stop there. Take [2, 1, 1, 2]. When right moves onto the trailing 2, the window still holds exactly two odd numbers, and two more subarrays appear, [1, 1, 2] and [2, 1, 1, 2]. Even numbers on the right give the same kind of extra freedom as even numbers on the left, and a walk that has already moved left forward can’t count them.

What actually decides a subarray. Only which k consecutive odd numbers it contains. The even numbers around them don’t change the odd count, so they only add freedom in where the subarray starts and where it ends. That suggests listing the positions of the odd numbers and working from that list.

In [2, 1, 1, 2] the odd numbers sit at indices 1 and 2. Put a marker at -1 before the first and one at 4, the array’s length, after the last, giving [-1, 1, 2, 4]. For the group of two odd numbers, 1 and 2:

start choices = 1 - (-1) = 2    (start at index 0 or 1)
end choices   = 4 - 2   = 2    (end at index 2 or 3)
count         = 2 * 2   = 4

The four subarrays are [1, 1], [2, 1, 1], [1, 1, 2], and [2, 1, 1, 2]. The two choices multiply because any start pairs with any end. The markers stand in for “no previous odd number” and “no next odd number”, so the first and last groups need no special case.

Take nums = [1, 1, 2, 1, 1], k = 3. The odd numbers sit at indices 0, 1, 3, 4, and with the markers the list is [-1, 0, 1, 3, 4, 5]. A window of size k = 3 slides over that list, one odd number at a time.

group of odd positions  start choices   end choices   product
0, 1, 3                 0 - (-1) = 1    4 - 3 = 1     1
1, 3, 4                 1 - 0 = 1       5 - 4 = 1     1

The total is 2, matching the two subarrays that contain exactly three odd numbers, [1, 1, 2, 1] and [1, 2, 1, 1]. This is a sliding window too, fixed at k odd positions wide, moving over the list of odd positions instead of over the array itself.

A more general route. Every subarray with at most k odd numbers either has exactly k or has at most k - 1, so the count with exactly k is the count with at most k minus the count with at most k - 1. “At most” passes the direction check, so each count is a plain window. Inside one, once [left, right] holds at most k odd numbers, every subarray ending at right and starting anywhere from left to right does too, which is right - left + 1 new subarrays per position of right.

On the same input, counting at most 3 odd numbers:

right  odds  left  new subarrays  running count
0      1     0     1              1
1      2     0     2              3
2      2     0     3              6
3      3     0     4              10
4      4->3  1     4              14

At right = 4 the fourth odd number pushes the count over the limit, so left drops the first 1, and the total is 14. Counting at most 2 the same way gives 12, and 14 - 12 = 2, the same answer. This version is longer here, but it carries over unchanged to problems like Subarrays with K Different Integers, where there’s no easy list of positions to slide over.

// Count Number of Nice Subarrays
// https://leetcode.com/problems/count-number-of-nice-subarrays/description/
//
// Problem: given an array of positive integers and an integer k,
// count the contiguous subarrays that contain exactly k odd numbers.
//
// "Exactly k" doesn't fit a window that grows and shrinks, a window
// with too few odd numbers and one with too many are both invalid,
// so no single direction of shrinking fixes both.
//
// What decides a subarray is only which k consecutive odd numbers it
// contains. Even numbers around them change nothing. So list the
// positions of the odd numbers, and slide a window of size k over
// that list. For each group of k odd positions, the subarray can
// start anywhere after the previous odd number up to the group's
// first odd, and end anywhere from the group's last odd up to just
// before the next odd number. Those two counts multiply.
//
// Markers at -1 and at nums.length stand in for "no previous odd"
// and "no next odd", so the first and last groups need no special case.

function numberOfSubarrays(nums, k) {
    const oddPositions = [-1];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] % 2 === 1) oddPositions.push(i);
    }
    oddPositions.push(nums.length);

    const realOdds = oddPositions.length - 2;
    let count = 0;

    // A group covers oddPositions[i] through oddPositions[i + k - 1].
    for (let i = 1; i + k - 1 <= realOdds; i++) {
        const leftChoices = oddPositions[i] - oddPositions[i - 1];
        const rightChoices = oddPositions[i + k] - oddPositions[i + k - 1];
        count += leftChoices * rightChoices;
    }

    return count;
}

// The general alternative: exactly k = (at most k) - (at most k - 1).
// Every subarray with at most k odd numbers either has exactly k or
// has at most k - 1. "At most" passes the direction check, so it is
// a plain window. Once [left, right] holds at most k odd numbers,
// every subarray ending at right and starting anywhere from left to
// right does too, which is right - left + 1 new subarrays.

function atMost(nums, k) {
    if (k < 0) return 0;

    let left = 0;
    let odds = 0;
    let count = 0;

    for (let right = 0; right < nums.length; right++) {
        if (nums[right] % 2 === 1) odds++;

        while (odds > k) {
            if (nums[left] % 2 === 1) odds--;
            left++;
        }

        count += right - left + 1;
    }

    return count;
}

function numberOfSubarraysBySubtraction(nums, k) {
    return atMost(nums, k) - atMost(nums, k - 1);
}

module.exports = { numberOfSubarrays, numberOfSubarraysBySubtraction };

Frequency of the Most Frequent Element gives an array and a budget k. One operation increases any element by 1, at most k operations are allowed, and the question is the highest frequency any single value can reach.

Read the statement the usual way. “Highest” is the max ask, the first signal. The second signal, a contiguous range, is nowhere in the statement. The array comes in whatever order it was given, and the elements that end up equal can come from any positions. This is a hidden window, one that only appears after a reframing, here a sort.

Increments only go up. Elements can only be raised, never lowered. So when a group of elements is made equal, the value they all end at is the group’s largest element. Raising the group past that only spends operations for nothing.

The cheapest group for a target. Raising an element to a target costs the target minus that element, so the elements closest below the target are the cheapest to raise. Once the array is sorted, the elements closest below a given element are exactly the ones just before it. So for a target sorted[right], the best group of any size is a stretch of the sorted array ending at right. That stretch is the window, and it exists only because the array was sorted first.

The cost is a formula, and it has to be derived. Raising every element in [left, right] up to sorted[right] costs the sum of the gaps:

(sorted[right] - sorted[left]) + (sorted[right] - sorted[left + 1]) + ... + (sorted[right] - sorted[right - 1])

Written without listing the gaps, that is sorted[right] * windowSize - windowSum. windowSum is the running value that gets added to as right grows and subtracted from as left shrinks, the same running sum used in the earlier problems. The window is valid while that cost stays within k.

What moves left. The direction check holds. Growing right to the next element can only raise the cost, since the array is sorted, the target gets bigger, and there is one more element to raise. Dropping from left can only lower it. So left moves while the cost is over k, and the answer is the largest window size seen.

Take nums = [1, 4, 8, 13], k = 5, already sorted.

right  window       cost                    valid?  left  best
0      [1]          1*1 - 1 = 0             yes     0     1
1      [1, 4]       4*2 - 5 = 3             yes     0     2
2      [1, 4, 8]    8*3 - 13 = 11           no      0     2
       [4, 8]       8*2 - 12 = 4            yes     1     2
3      [4, 8, 13]   13*3 - 25 = 14          no      1     2
       [8, 13]      13*2 - 21 = 5           yes     2     2

At right = 2, raising 1 and 4 up to 8 costs 11, over the budget, so left drops the 1, and the window [4, 8] costs 4. At right = 3, the same thing happens again. The best window stays at size 2, the known answer for this input.

// Frequency of the Most Frequent Element
// https://leetcode.com/problems/frequency-of-the-most-frequent-element/description/
//
// Problem: in one operation, increase any element by 1. With at most
// k operations, return the highest frequency any single value can
// reach.
//
// Increments only go up, so a group of elements can only be raised
// to the group's largest value. The cheapest group of a given size
// to raise to a target is the elements closest to it just below it,
// which is a contiguous stretch once the array is sorted. That is
// what makes sorting first the right move, and what makes a window
// over the sorted array valid.
//
// The condition that moves left is a cost, not a count or a sum on
// its own. Raising every element in a window to the value at right
// costs nums[right] * windowSize - windowSum, and the window is
// valid while that stays within k.
//
// Growing right can only raise that cost (the array is sorted, so
// the target only gets bigger), and dropping from left can only
// lower it, so shrinking from the left is safe.

function maxFrequency(nums, k) {
    const sorted = [...nums].sort((a, b) => a - b);
    let left = 0;
    let windowSum = 0;
    let best = 1;

    for (let right = 0; right < sorted.length; right++) {
        windowSum += sorted[right];

        while (sorted[right] * (right - left + 1) - windowSum > k) {
            windowSum -= sorted[left];
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

module.exports = { maxFrequency };

Grumpy Bookstore Owner gives the number of customers arriving each minute, and for each minute whether the owner is grumpy, in which case those customers leave unsatisfied. The owner can stay calm for minutes consecutive minutes, once, and the goal is the maximum number of satisfied customers.

Read the statement the usual way. “Maximum” is the max ask. The contiguous range is written right in the statement, minutes consecutive minutes, and its size is handed over. So this is the fixed-size shape, and unlike the last few problems there is no hidden window to find. The work here is deciding what the window should track. It takes five steps, on customers = [1, 0, 1, 2, 1, 1, 7, 5], grumpy = [0, 1, 0, 1, 0, 1, 0, 1], minutes = 3.

1. What the problem says. Each minute, some customers walk in, and the owner is either calm (0) or grumpy (1). Customers who arrive while the owner is grumpy leave unhappy. The owner can pick one stretch of 3 minutes in a row and stay calm for all of them. The goal is the most happy customers possible.

2. Start with no technique at all. Only customers arriving in calm minutes are happy. Minutes 0, 2, 4, 6 are calm, so 1 + 1 + 1 + 7 = 10. Call that the baseline. It doesn’t depend on where the stretch goes, since the technique can never make anyone unhappy.

3. What the technique actually changes. Inside the chosen stretch, a minute that was already calm stays the same, its customers were happy already. A minute that was grumpy becomes calm, so its customers flip from unhappy to happy. The gain from a stretch is therefore only the customers in grumpy minutes inside it. The total is the baseline plus the gain, so the best total comes from the stretch with the biggest gain.

4. Now it is a window question. Write out the customers in grumpy minutes, with 0 for calm minutes, [0, 0, 0, 2, 0, 1, 0, 5]. The gain of any 3-minute stretch is the sum of 3 neighbors in that list:

minutes 0-2: 0
minutes 1-3: 2
minutes 2-4: 2
minutes 3-5: 3
minutes 4-6: 1
minutes 5-7: 6   <- biggest

The best gain is 6, so the answer is 10 + 6 = 16. The window is 3 wide, given by the problem, and it asks for the largest sum, the fixed-size shape.

5. Sliding instead of re-adding. Adding 3 numbers for every stretch is the same repeated work as before. Moving the stretch by one minute changes only two things, one minute leaves and one enters. So the gain is adjusted by adding the entering minute’s customers if that minute is grumpy, and subtracting the leaving minute’s customers if that minute was grumpy. left moves when the window would be longer than minutes, the same as in Maximum Average Subarray. The window tracks only the extra, not the total, with the calm customers sitting outside it as a fixed baseline. Starting from the first window, minutes 0 to 2, with a gain of 0:

right  enters  leaves  gain  best gain
3      2       0       2     2
4      0       0       2     2
5      1       0       3     3
6      0       2       1     3
7      5       0       6     6

An entering value only counts if that minute is grumpy, and a leaving value only comes out if it was counted. The best gain is 6, the window covering minutes 5 to 7, so the answer is 10 + 6 = 16.

// Grumpy Bookstore Owner
// https://leetcode.com/problems/grumpy-bookstore-owner/description/
//
// Problem: customers[i] people enter during minute i. If grumpy[i]
// is 1, the owner is grumpy that minute and those customers leave
// unsatisfied. The owner can use a technique once, staying calm for
// `minutes` consecutive minutes. Return the maximum number of
// satisfied customers.
//
// Some customers are satisfied no matter what, the ones arriving
// while the owner is calm. That is a fixed baseline. The technique
// only changes customers arriving during grumpy minutes inside its
// window, so the gain of a window is the customers in grumpy minutes
// inside it. The window tracks only that gain, not the total.
// Fixed size, `minutes`, maximize the gain. The answer is the
// baseline plus the best gain.

function maxSatisfied(customers, grumpy, minutes) {
    let baseline = 0;
    for (let i = 0; i < customers.length; i++) {
        if (grumpy[i] === 0) baseline += customers[i];
    }

    let gain = 0;
    for (let i = 0; i < minutes; i++) {
        if (grumpy[i] === 1) gain += customers[i];
    }
    let bestGain = gain;

    for (let right = minutes; right < customers.length; right++) {
        // The entering minute only adds to the gain if it is grumpy.
        if (grumpy[right] === 1) gain += customers[right];
        // The leaving minute only comes out if it was counted.
        if (grumpy[right - minutes] === 1) gain -= customers[right - minutes];
        bestGain = Math.max(bestGain, gain);
    }

    return baseline + bestGain;
}

module.exports = { maxSatisfied };

Binary Search: Asking the Right Questions

Seeing it in a statement

Every problem statement has two parts. What it asks for, the shape of the answer. What it offers, the structure in the input we can lean on. The pattern is where the two meet.

If one check only rules out the element it touched and not a whole side, it is not binary search. Check Two Pointers.

A number, not a piece of the array. Sliding window answers which stretch, or how long. Two pointers answers which pair, or which positions. When the answer is a quantity, a day, a speed, a capacity, a distance, it is binary search on the answer, even if the statement also talks about adjacent elements or subarrays. Those belong to the check, not to the answer.

A guess that is easy to check. When checking a guessed answer is easy and finding the answer directly is hard, the problem is a guessing problem, and binary search is guessing done well. Every guess that turns out wrong removes half of the remaining range, so a good guess is reached in a few steps.

A maximum hidden in plain sight. Some statements ask for a minimum and never say “maximum”, yet are a minimum of a maximum. “The minimum days to wait” before flowers can be used means waiting for the last of them to bloom, the largest bloom day among the flowers chosen. The answer is the choice whose largest is smallest.

Five problems follow, each read from its statement to the pattern. No code here, the code lives in Implementation and Examples.

1. Search a 2D Matrix

The statement. Search a 2D Matrix gives a grid where each row is sorted and the first value of each row is bigger than the last value of the row above, and asks whether a target is in the grid.

Asks for. Whether a target is in the grid.

Offers. Sorted rows, each starting above where the last ended. Together they make one sorted list cut into rows.

Why it fits. Read the grid row by row, and the values never decrease from the first cell to the last. Number the cells in that order, and every number maps to a row and a column, the row from how many full rows come before it and the column from what is left over. So the candidates are those numbers, the question at each one is whether its value is at least the target, and the answers flip once, exactly as in a sorted array. The grid shape is only a way of storing the list.

2. Find Minimum in Rotated Sorted Array

The statement. Find Minimum in Rotated Sorted Array gives an array of distinct values that was sorted and then rotated, so [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2], and asks for the smallest value.

Asks for. The minimum value.

Offers. A sorted array, rotated, so order is broken in exactly one place, and the minimum sits right after that break.

Why it fits. The array is two sorted blocks, every value in the first block is bigger than every value in the second, and the minimum is where the second block starts. Ask of each index whether its value is at most the last value of the array. Every index in the first block says no, every index in the second says yes, so the answers flip once and the minimum is the first yes. Checking the middle against the last value tells us which block the middle is in, and that settles a whole side.

3. Find Peak Element

The statement. Find Peak Element gives an array with no two equal neighbors and asks for the index of any peak, a value bigger than both its neighbors, with the space beyond each end counted as lower than everything.

Asks for. Any one peak, in O(log n).

Offers. Edges that count as -INF, so walking uphill always ends on a peak, and permission to return any peak, so a side only has to be guaranteed to hold one.

Why it fits. The first instinct is a single pass, walk left to right and return the first element bigger than the one after it. That is correct, and without the O(log n) requirement it would be the answer. The requirement is what pushes us to look for a way to discard half the array at once.

Picture the array padded as [-INF, ...array..., -INF]. Two extreme cases show what the padding does. In [-INF, 1, 2, 3, 4, 5, -INF] the values only rise, and the peak is the 5 at the right end, since it is bigger than the -INF after it. In [-INF, 5, 4, 3, 2, 1, -INF] the values only fall, and the peak is the 5 at the left end, since it is bigger than the -INF before it. Whichever way the values run, the climb ends on a peak at the side it rises toward. Now compare the middle with its right neighbor. If the neighbor is bigger, walk right from it. Each next value is either smaller, and the current one is a peak, or bigger, and the walk climbs on. The climb cannot go past the -INF at the end, so it always stops on a peak. The right side is guaranteed to hold one, and the left side is discarded. If the neighbor is smaller, the same walk runs leftward from the middle.

The discarded side may hold a peak too. On [1, 2, 1, 2, 3, 4, 5] the search goes right and returns the 5, never visiting the peak at index 1. That is allowed because the problem accepts any peak.

Peaks being scattered is not what makes this work. Scattered answers on their own force a full scan. Asked for the global maximum of the same array, binary search fails, since the uphill side might hold a small peak while the maximum sits on the other side. What makes it work is “any peak” together with the -INF edges, which turn one comparison into a guarantee about one side. Sorted order is one way to get that guarantee, and this is another.

4. Koko Eating Bananas

The statement. Koko Eating Bananas gives an array piles of n piles, where piles[i] is the number of bananas in the ith pile, and a number of hours h. Koko picks an eating speed k, bananas per hour. Each hour she chooses one pile and eats k bananas from it. If the pile has fewer than k left, she finishes it and waits out the rest of that hour. It asks for the smallest k that lets her finish every pile within h hours. For piles = [3, 6, 7, 11] and h = 8, the answer is 4. At speed 4 the piles take 1, 2, 2, and 3 hours, 8 in total. At speed 3 they take 1, 2, 3, and 4, which is 10, too many.

Asks for. The smallest speed that finishes in time.

Offers. A yes or no test for any guessed speed, and a speed that works keeps working when faster. No array, the answer is a number in a range.

Why it fits. The candidates are every speed from 1 up to the size of the largest pile. Koko eats from only one pile per hour, so every pile costs at least one hour. At a speed equal to the largest pile, every pile takes exactly one hour, and no faster speed can bring a pile below that. If a speed is too slow, every lower speed is too slow as well, and if a speed works, every higher one works too. So the answers run no, then yes, flipping once, and the answer is the first yes. Each guess is tested by working out the hours it would take, and every test settles half of the remaining speeds.

5. Magnetic Force Between Two Balls

The statement. Magnetic Force Between Two Balls gives an array position of n baskets, where position[i] is where the ith basket sits on a line, and a number of balls m. Each basket holds at most one ball. The force between two balls is the distance between their baskets. All m balls have to be placed, and among all pairs of balls, the smallest distance is what counts. It asks for the largest that smallest distance can be. For position = [1, 2, 3, 4, 7] and m = 3, the answer is 3. Balls at 1, 4, and 7 are 3 apart each. A gap of 4 does not work, since after 1 the next basket at least 4 away is 7, and there is no room for a third ball.

Asks for. The largest possible minimum gap between balls.

“Largest minimum” reads oddly at first. The balls can be placed in many arrangements, and each arrangement has its own smallest gap, min1, min2, min3, and so on. The answer is the arrangement whose smallest gap is the biggest. On position = [1, 2, 3, 4, 7] with m = 3, balls at 1, 2, 3 have a smallest gap of 1, at 1, 3, 7 it is 2, and at 1, 4, 7 it is 3. The largest of these is 3.

“Smallest maximum” is the mirror image, and it shows up just as often. Each arrangement has its own largest value, max1, max2, max3, and the answer is the arrangement whose largest value is the least. Split Array Largest Sum is this form, every way of splitting the array has a biggest part sum, and the answer is the split whose biggest part sum is smallest. Both phrasings point to binary search on the answer.

Offers. A yes or no test for any guessed gap. Maximizing a minimum directly is hard, but checking whether a gap is achievable is easy.

Why it fits. Guess a gap and ask whether all the balls fit with at least that much space between each pair. To test it, sort the positions, place a ball in the first basket, and keep placing each next ball in the first basket at least that gap away. Placing each ball as early as possible always leaves the most room for the rest. If a gap is achievable, every smaller gap is too, and if it is not, no larger gap is. The answers run yes, then no, flipping once, and the answer is the last yes. Sorting here is part of the test, not the thing being searched.

Building the range when the statement gives none

Koko and Magnetic Force hand over no array to search. The range of candidates has to be built from the statement, and two questions about the answer build it. What is the smallest value the answer could ever be, which becomes low. What is the largest value it could ever be, which becomes high.

For Koko, a speed of 0 never finishes anything, so low is 1. A speed equal to the largest pile finishes every pile in one hour, the fastest possible, so high is the largest pile. For Magnetic Force, positions are distinct whole numbers, so any two balls are at least 1 apart and low is 1. No two balls can be further apart than the two outermost baskets, so high is the distance between them.

The range only has to contain the answer, it does not have to be tight. Each check halves what is left, so a loose bound costs only a few extra checks. When unsure, a bound that is obviously safe beats a clever one that might cut the answer off.

With the range built, the middle of it is a candidate answer, and the check says whether it is valid. A valid middle might be the answer, so it is recorded before the search moves on. Where the search moves depends on whether the problem wants the smallest valid value or the largest.

For Koko, a speed that works means every faster speed works too, so the only open question is whether a slower one also works. A speed that fails means every slower speed fails too, so the answer must be faster. Take piles = [3, 6, 7, 11] and h = 8, with the range [1, 11].

low  high  mid  hours  valid?  action
1    11    6    6      yes     record 6, search left
1    5     3    10     no      search right
4    5     4    8      yes     record 4, search left
4    3     stop, the answer is 4

What the five share

In every one, a single candidate can be tested with a yes or no, an index, a speed, a gap. The answers across all the candidates flip only once, or at least one side is guaranteed to hold an answer, so one check discards a whole side. The candidates are either positions in an array, sorted outright, sorted in pieces, or not sorted at all, or the possible values of the answer itself. When a check can only rule out the one element it touched, the problem is closer to Two Pointers.

Implementation

There is no special type for binary search, just two numbers marking the current range.

let low = 0;
let high = nums.length - 1;

The pattern lives in how low and high move toward each other based on what the middle tells us. One loop underlies every shape here. low and high mark the current range, mid gets checked once per iteration, and a single comparison decides which half survives. The loop ends when there’s nothing left to check.

Classic search

Looking for an exact value in a sorted array.

function binarySearch(nums, target) {
    let low = 0;
    let high = nums.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

mid is fully resolved the moment it’s checked, equal, too small, or too big, so it never needs to be looked at again. That’s why both low = mid + 1 and high = mid - 1 move past mid itself.

First or last occurrence

When duplicates exist and the goal is the leftmost or rightmost match, a match found isn’t the end of the search. It gets recorded, and the search keeps narrowing toward the edge in case a better one is still hiding on that side.

function leftmostOccurrence(nums, target) {
    let low = 0;
    let high = nums.length - 1;
    let result = -1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (nums[mid] === target) {
            result = mid;
            high = mid - 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result;
}

The only change from classic search is that an equal match narrows high instead of returning immediately, since an earlier occurrence, if one exists, can only be further left.

Search on answer

There’s no array to index into here. low and high bound a range of candidate answers instead, and a feasibility check replaces the equality check.

function minimumFeasible(low, high, isFeasible) {
    while (low < high) {
        const mid = Math.floor((low + high) / 2);

        if (isFeasible(mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }

    return low;
}

mid might be the answer itself here, so a feasible mid sets high = mid, keeping it in play, rather than excluding it the way high = mid - 1 did in classic search. The loop runs while low < high and stops the moment they meet, and that shared value is the smallest candidate that passed the check.

The one thing that actually matters

Every version of this loop makes the same move, check one candidate, discard a whole half. What changes between problems is what “resolved” means for mid, an exact equality, a direction to narrow toward an edge, or a feasibility check, and whether what’s being searched is a real array or a range of candidate answers with no array behind it at all. Once that check is written correctly, the loop around it barely changes.

Binary Search: Examples

Worked problems from the questions chapter, reasoning and code together, one shape at a time.

Classic Search

Find First and Last Position of Element in Sorted Array gives a sorted array nums and a target, and asks for the first and last index where target appears, or [-1, -1] if it never does, in O(log n). For nums = [5, 7, 7, 8, 8, 10] and target = 8, the answer is [3, 4].

Reading the statement for signals, the array is sorted and the required time is O(log n), which a scan cannot reach. Comparing nums[mid] to target tells us which side to discard, so the check from Question 1 comes free from the sort order. This is the classic shape. Cleary a Binary Search Problem

The brute force scans from the left for the first match and from the right for the last, O(n). Sorting does something useful for the structure of the answer, though. Every copy of target sits in one unbroken block, so the answer is not a search for copies, it is a search for the two edges of that block.

A plain binary search returns the moment it finds a match, and here that is the wrong move. On [8, 8, 8, 8] with target = 8, the first mid is index 1, a match, and it is neither edge. A match at mid proves only that the block touches mid. The left edge is at mid or somewhere to its left, and the right edge is at mid or somewhere to its right.

So a match is recorded and the search continues instead of stopping. To find the left edge, record mid and set high = mid - 1, since anything better can only sit on the left. If another copy is found there, the record moves left. If none is, the record stays where it was. The right edge is the mirror image, record mid and set low = mid + 1. Two searches, each O(log n), and the answer is the pair of records.

This is the check that flips once from Question 2, with the equal case folded in. For the left edge the question at each index is whether nums[i] is at least target, false up to a point and true after it, and the left edge is the first true index, provided it holds target. If no index holds target, the record is never set and stays -1.

Take nums = [5, 7, 7, 8, 8, 10], target = 8. The left edge search:

low  high  mid  nums[mid]  action               result
0    5     2    7          too small, low = 3   -1
3    5     4    8          match, high = 3      4
3    3     3    8          match, high = 2      3

low is now 3 and high is 2, so the search stops with result = 3. The right edge search:

low  high  mid  nums[mid]  action               result
0    5     2    7          too small, low = 3   -1
3    5     4    8          match, low = 5       4
5    5     5    10         too big, high = 4    4

low is now 5 and high is 4, so the search stops with result = 4. The answer is [3, 4].

// Find First and Last Position of Element in Sorted Array
// https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/
//
// Problem: nums is sorted. Return the first and last index of target,
// or [-1, -1] if it is absent, in O(log n).
//
// Sorted order puts every copy of target in one block, so the answer is
// the two edges of that block. A match at mid only proves the block
// touches mid, so it is recorded and the search keeps narrowing toward
// the edge being looked for. One search per edge.

function searchRange(nums, target) {
    return [findEdge(nums, target, true), findEdge(nums, target, false)];
}

function findEdge(nums, target, wantLeft) {
    let low = 0;
    let high = nums.length - 1;
    let result = -1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (nums[mid] === target) {
            result = mid;
            // A better match can only sit on the side of the edge we want.
            if (wantLeft) high = mid - 1;
            else low = mid + 1;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return result;
}

module.exports = { searchRange };

Search in Rotated Sorted Array gives an array of distinct values that was sorted ascending and then rotated at an unknown pivot, and asks for the index of target, or -1, in O(log n). For nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the answer is 4.

The O(log n) requirement and the near-sorted array point at binary search. The array is not sorted, though, and that removes the free check. On the example, the first mid is index 3, value 7, which is bigger than 0. Classic search reads that as “too big, discard the right half,” and the right half is where 0 is. Comparing nums[mid] to target no longer says which side holds the answer.

The brute force is a scan, O(n). To do better, we need something true about every split that the broken sort order does not take away. A rotation moves a block from the front to the back, which creates exactly one drop point, one place where a large value is followed by a small one. In [4, 5, 6, 7, 0, 1, 2] it sits between 7 and 0. That drop can only be in one of the two halves at mid, so the other half has no drop inside it and is sorted.

A sorted half is enough, because a sorted half gives back the check we lost. If the left half is sorted and nums[low] <= target < nums[mid], then target is in the left half or nowhere, so the right half is discarded. If target falls outside that range, it cannot be in the sorted half at all, so the sorted half is discarded and the search moves to the other one. Every step still throws away a whole half, so the time stays O(log n).

That leaves one question, which half is sorted. If nums[low] <= nums[mid], the left half has no drop inside it, since its first value is not bigger than its last. Otherwise the drop is in the left half, and the right half is the sorted one. The comparison uses <= so that a left half holding a single element, where low and mid are the same index, counts as sorted. Distinct values matter here, since with duplicates nums[low], nums[mid], and nums[high] can all be equal and the comparison no longer says where the drop is.

Take nums = [4, 5, 6, 7, 0, 1, 2] and target = 0.

low  high  mid  nums[mid]  sorted half  target in it?  action
0    6     3    7          left [4..7]  no             low = 4
4    6     5    1          left [0..1]  yes            high = 4
4    4     4    0          match, return 4

At the first step the left half [4, 5, 6, 7] is sorted, and 0 is not between 4 and 7, so 0 can only be in the right half. At the second step [0, 1] is sorted and 0 is in its range, so the right side is discarded.

The right half being the sorted one needs its own trace. Take nums = [6, 7, 0, 1, 2, 4, 5] and target = 5.

low  high  mid  nums[mid]  sorted half   target in it?  action
0    6     3    1          right [1..5]  yes            low = 4
4    6     5    4          left [2..4]   no             low = 6
6    6     6    5          match, return 6

At the first step nums[low] = 6 is bigger than nums[mid] = 1, so the drop is in the left half and the right half [1, 2, 4, 5] is sorted. 5 is within 1 to 5, so the left half is discarded.

// Search in Rotated Sorted Array
// https://leetcode.com/problems/search-in-rotated-sorted-array/description/
//
// Problem: nums is sorted ascending with distinct values, then rotated
// at an unknown pivot. Return the index of target, or -1, in O(log n).
//
// Comparing nums[mid] to target alone no longer says which side to
// discard. What still holds is that the rotation's single drop sits in
// at most one half, so the other half is sorted. Find the sorted half,
// test target against its range, and discard accordingly.

function search(nums, target) {
    let low = 0;
    let high = nums.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (nums[mid] === target) return mid;

        if (nums[low] <= nums[mid]) {
            // Left half is sorted, so its range is a trustworthy check.
            if (nums[low] <= target && target < nums[mid]) high = mid - 1;
            else low = mid + 1;
        } else {
            // Right half is sorted.
            if (nums[mid] < target && target <= nums[high]) low = mid + 1;
            else high = mid - 1;
        }
    }

    return -1;
}

module.exports = { search };

Single Element in a Sorted Array gives a sorted array where every value appears exactly twice except one, which appears once, and asks for that value in O(log n) time and O(1) space. For nums = [1, 1, 2, 3, 3, 4, 4, 8, 8], the answer is 2.

Asks for. The value that appears once, in O(log n).

Offers. A sorted array, so equal values sit next to each other in pairs.

The O(log n) requirement points at binary search, but there is no target. Comparing nums[mid] with anything outside the array says nothing, so the yes or no question has to come from somewhere else. Writing out the indices shows where.

index  0  1  2  3  4  5  6  7  8
value  1  1  2  3  3  4  4  8  8

Before the 2, the pair (1, 1) starts on index 0, an even index. After the 2, the pairs start on 3, 5, and 7, all odd. The single element takes up one position, and that shifts every pair after it by one. So the structure of the indices changes at exactly one place, the single element.

The same fact reads more simply as a count. Take mid’s pair and count the elements to its left. If the single element is not among them, they are all complete pairs, and the count is even. If it is among them, the count is odd. So an even count sends the search right and an odd count sends it left. Across the array the answers to “is the count even” run yes, yes, and then no from the single element onward, flipping once.

At each mid there are three cases. If nums[mid] equals the element before it, the pair is (mid - 1, mid), and mid - 1 elements sit to its left. If it equals the element after it, the pair is (mid, mid + 1), and mid elements sit to its left. If it equals neither, nums[mid] is the single element, and the search returns it.

low  high  mid  nums[mid]  pair    left count  action
0    8     4    3          (3, 4)  3, odd      high = 3
0    3     1    1          (0, 1)  0, even     low = 2
2    3     2    2          none                return 2

This is a third source of the one-flip property. Sorted values give it in the classic search, a feasibility test gives it when searching on the answer, and here it comes from counting the elements left of a pair.

// Single Element in a Sorted Array
// https://leetcode.com/problems/single-element-in-a-sorted-array/description/
//
// Problem: nums is sorted, every value appears exactly twice except one,
// which appears once. Return that value in O(log n) time and O(1) space.
//
// Find mid's pair, then count the elements to the left of that pair. An
// even count means the left side is made only of complete pairs, so the
// single element is on the right. An odd count means it is on the left.

function singleNonDuplicate(nums) {
    let low = 0;
    let high = nums.length - 1;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        let leftCount;
        if (nums[mid] === nums[mid - 1]) {
            leftCount = mid - 1;
        } else if (nums[mid] === nums[mid + 1]) {
            leftCount = mid;
        } else {
            return nums[mid];
        }

        if (leftCount % 2 === 0) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
}

module.exports = { singleNonDuplicate };

Search on Answer

The split shape

Several problems in this section share one shape. There is an array arr and a number x, and the array has to be broken into x contiguous subarrays, in order. There are many ways to do it. On arr = [1, 2, 3] with x = 2, one way is [1, 2] and [3], another is [1] and [2, 3].

Each way gives a list of subarray sums, and each list has a largest value. Call these max1, max2, and so on, one per way. The answer is the smallest of them, the minimum of the maximums.

way 1: [1, 2] [3]   sums 3, 3   max 3
way 2: [1] [2, 3]   sums 1, 5   max 5
answer: min(3, 5) = 3

Trying every way does not scale, since the number of ways grows very fast with the size of the array. The move that makes this solvable is to stop searching through the ways and guess the answer instead. Pick a value C and ask a yes or no question, is there a way to split the array so that every subarray sum is at most C.

That question has an easy answer. Fill each subarray as full as possible without going over C, and start a new one only when the next element would push it over. Filling each subarray as full as it can go always leaves the fewest elements for the rest, so if this uses at most x subarrays, C works, and if it uses more, no way works.

The guesses flip once. If every subarray fits under C, the same split fits under C + 1, so once a guess works, every bigger guess works too. That makes it a search on the answer, for the smallest C that works.

The range comes from the array. Some subarray has to hold the largest element, so the answer is at least max(arr), which becomes low. A single subarray holding everything has sum sum(arr), which becomes high. So for any problem with this shape, the range is [max(arr), sum(arr)]. Other answer-range problems build their range differently, as Koko and Magnetic Force do on the questions page. A middle value that works is recorded, and the search goes left for something smaller. A middle value that fails sends the search right.

Splitting into “at most x” pieces and “exactly x” pieces give the same answer. A piece with two or more elements can always be split in two without raising the largest sum, so a split with fewer pieces can be turned into one with exactly x.

Capacity To Ship Packages Within D Days

Capacity To Ship Packages Within D Days gives an array weights, where weights[i] is the weight of the ith package, and a number of days days. Each day, a ship loads packages in the given order, never skipping one, until the next package would push the load over the ship’s capacity. It asks for the smallest capacity that ships every package within days days. For weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and days = 5, the answer is 15.

Asks for. The smallest capacity that works.

Offers. A yes or no test for any guessed capacity, load the packages day by day and count the days.

This is the split shape with different names. The packages are arr, the days are x, and each day’s load is one subarray. The capacity a split needs is its heaviest day, so the answer is the split whose heaviest day is the lightest.

At capacity 15, the days fill like this.

day 1: 1 2 3 4 5   = 15
day 2: 6 7         = 13
day 3: 8           = 8
day 4: 9           = 9
day 5: 10          = 10

The range is low = 10, the heaviest package, and high = 55, the total.

low  high  mid  days needed  works?  action
10   55    32   2            yes     record 32, search left
10   31    20   4            yes     record 20, search left
10   19    14   6            no      search right
15   19    17   4            yes     record 17, search left
15   16    15   5            yes     record 15, search left
15   14    stop, the answer is 15

At 14, the packages need six days, one too many, and at 15 they fit in five, so 15 is the smallest capacity that works.

// Capacity To Ship Packages Within D Days
// https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/
//
// Problem: weights[i] is the weight of the ith package. Each day the ship
// loads packages in order, never skipping one, without going over its
// capacity. Return the smallest capacity that ships everything within
// `days` days.
//
// Every way of splitting the packages into days has a heaviest day, and
// the answer is the split whose heaviest day is lightest. Trying every
// split is hopeless, so guess a capacity instead and check whether it
// works. A capacity that works keeps working when bigger, so the answers
// flip once, and the smallest one that works is found by binary search.

function shipWithinDays(weights, days) {
    let low = Math.max(...weights);
    let high = weights.reduce((sum, w) => sum + w, 0);
    let answer = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (daysNeeded(weights, mid) <= days) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return answer;
}

// Fill each day as full as possible, then start the next one.
function daysNeeded(weights, capacity) {
    let count = 1;
    let load = 0;

    for (const w of weights) {
        if (load + w > capacity) {
            count++;
            load = 0;
        }
        load += w;
    }

    return count;
}

module.exports = { shipWithinDays };

Minimum Number of Days to Make m Bouquets

Minimum Number of Days to Make m Bouquets gives an array bloomDay, where bloomDay[i] is the day flower i blooms, and two numbers m and k. A bouquet needs k adjacent flowers that have all bloomed, and each flower can go in at most one bouquet. It asks for the smallest number of days to wait before m bouquets can be made, or -1 if that is impossible. For bloomDay = [7, 7, 7, 7, 12, 7, 7], m = 2, and k = 3, the answer is 12.

Asks for. The smallest day that works.

Offers. A yes or no test for any guessed day, count the runs of bloomed flowers and the bouquets each run gives.

The answer is a day, a number, not a stretch of flowers, which points at binary search on the answer even though the statement talks about adjacent flowers. The adjacent flowers belong to the check. The maximum is hidden too. Waiting for a bouquet means waiting for its last flower to bloom, so the wait for a set of bouquets is the largest bloom day among their flowers, and the answer is the choice whose largest is smallest.

This is not the split shape, so the range is not [max(arr), sum(arr)]. It comes from the bloom days. Before the earliest bloom day nothing has bloomed, so low is min(bloomDay). By the latest bloom day every flower has bloomed, so high is max(bloomDay), and if m bouquets cannot be made by then, they never can.

The answers flip once because flowers never un-bloom. A flower open on day d is still open on day d + 1, so every bouquet possible on day d is still possible later. Once a day works, every later day works.

Whether the answer is -1 is known before searching. m bouquets of k flowers need m * k flowers, and if the array has fewer than that, no day works. If it has enough, the latest bloom day always works, so the search always finds an answer.

The check walks the flowers once. A bloomed flower adds to the current run, and when the run reaches k, that is one bouquet and the run starts over. A flower not yet bloomed breaks the run.

low  high  mid  bloomed by mid      runs   bouquets  works?  action
7    12    9    all except the 12   4, 2   1         no      search right
10   12    11   all except the 12   4, 2   1         no      search right
12   12    12   all                 7      2         yes     record 12, search left
12   11    stop, the answer is 12

On days 9 and 11 the 12 splits the flowers into a run of four and a run of two, which gives one bouquet, since the run of four only holds one group of three. On day 12 the run is all seven flowers, which holds two groups of three.

// Minimum Number of Days to Make m Bouquets
// https://leetcode.com/problems/minimum-number-of-days-to-make-m-bouquets/description/
//
// Problem: bloomDay[i] is the day flower i blooms. A bouquet needs k
// adjacent bloomed flowers, and each flower goes in at most one bouquet.
// Return the smallest day by which m bouquets can be made, or -1.
//
// The answer is a day, so guess one and check it. A day that works keeps
// working on every later day, since flowers never un-bloom. The range is
// from the earliest bloom to the latest, and if m bouquets need more
// flowers than exist, no day works at all.

function minDays(bloomDay, m, k) {
    if (m * k > bloomDay.length) return -1;

    let low = Math.min(...bloomDay);
    let high = Math.max(...bloomDay);
    let answer = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (bouquetsBy(bloomDay, k, mid) >= m) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return answer;
}

// Count runs of bloomed flowers, taking a bouquet every time a run reaches k.
function bouquetsBy(bloomDay, k, day) {
    let bouquets = 0;
    let run = 0;

    for (const d of bloomDay) {
        if (d <= day) {
            run++;
            if (run === k) {
                bouquets++;
                run = 0;
            }
        } else {
            run = 0;
        }
    }

    return bouquets;
}

module.exports = { minDays };

Kth Smallest Element in a Sorted Matrix

Kth Smallest Element in a Sorted Matrix gives an n × n matrix where every row and every column is sorted ascending, and a number k. It asks for the kth smallest element in sorted order, counting duplicates. For the matrix below and k = 8, the answer is 13, since all the values sorted are 1, 5, 9, 10, 11, 12, 13, 13, 15.

[[ 1,  5,  9],
 [10, 11, 13],
 [12, 13, 15]]

Asks for. A value, the kth smallest.

Offers. Sorted rows and sorted columns, and a count of the elements at or below any guessed value that is easy to work out.

The matrix is not one sorted list, which rules out searching by position. In reading order it is 1, 5, 9, 10, 11, 13, 12, 13, 15, and 13 comes before 12. With k = 6, the 6th smallest is 12, but the 6th position in reading order holds 13. Search a 2D Matrix could search positions only because each row starts after the previous row ends, and this matrix makes no such promise.

So the search runs over values instead. The smallest value is the top-left corner and the largest is the bottom-right corner, which gives low = matrix[0][0] and high = matrix[n - 1][n - 1]. mid is a value, often one that does not appear in the matrix at all, never a position.

The check asks how many elements are at or below mid. If the count is at least k, mid is big enough, so it is recorded and the search goes left for something smaller. If the count is less than k, the search goes right. The answers flip once, since raising mid can only raise the count.

The answer always ends up being an element of the matrix, even though most guesses are not. The search finds the smallest value whose count reaches k. If that value were not in the matrix, the value just below it would have exactly the same count, so it would pass too, and the first value would not be the smallest after all.

The first way to count is row by row, starting at [0, 0]. Each row is sorted, so two shortcuts apply. If a row’s last element is at or below mid, the whole row counts, all n of it, without looking at the rest. If a row’s first element is already above mid, nothing in it counts, and since the columns are sorted too, every row below starts even bigger, so the count is finished. Only the rows that mid cuts through the middle need walking, from the left until the first value above mid.

That is correct, but when mid cuts through every row, it still walks close to every cell, about n² steps per check. The walking can be shared between rows. Where a row stops counting can only move left as we go down, because each row is bigger than the one above it, column by column. So there is no need to restart each row from the left.

Start at the top-right corner instead, the end of the first row. If the cell is at or below mid, every cell to its left in that row is smaller still, so the row counts up to there, col + 1 elements, and the walk steps down to the next row. If the cell is above mid, the walk steps left. The walk never moves right again, since the next row’s stopping point can only be further left. From this corner, left always means smaller and down always means bigger, so every cell gives a clear direction, which the top-left corner does not, since both right and down mean bigger. Each step leaves a row or a column behind, so a count takes at most 2n steps.

For mid = 12, the walk goes like this.

(0, 2) = 9   at or below 12   row 0 counts 3 (1, 5, 9), step down
(1, 2) = 13  above 12         step left
(1, 1) = 11  at or below 12   row 1 counts 2 (10, 11), step down
(2, 1) = 13  above 12         step left
(2, 0) = 12  at or below 12   row 2 counts 1 (12), step down, done
count = 6

low  high  mid  count at or below mid  action
1    15    8    2                      too few, search right
9    15    12   6                      too few, search right
13   15    14   8                      enough, record 14, search left
13   13    13   8                      enough, record 13, search left
13   12    stop, the answer is 13

8 and 14 were both guessed and neither is in the matrix. 14 passed, but 13 passed with the same count, so the search kept going left until it landed on 13, which is.

// Kth Smallest Element in a Sorted Matrix
// https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/
//
// Problem: an n x n matrix with every row and column sorted ascending.
// Return the kth smallest element in sorted order, counting duplicates.
//
// The matrix is not one sorted list, so positions cannot be searched.
// Values can. Guess a value and count the elements at or below it. The
// count only grows as the guess grows, and the smallest value whose
// count reaches k is the answer, always an element of the matrix.

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let low = matrix[0][0];
    let high = matrix[n - 1][n - 1];
    let answer = high;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (countAtMost(matrix, mid) >= k) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return answer;
}

// First version: count row by row. A row whose last element fits counts
// whole, a row whose first element is too big ends the count, and only
// the rows in between are walked. Up to n * n steps.
function countAtMostByRows(matrix, value) {
    const n = matrix.length;
    let count = 0;

    for (let row = 0; row < n; row++) {
        if (matrix[row][0] > value) break;
        if (matrix[row][n - 1] <= value) {
            count += n;
            continue;
        }
        for (let col = 0; col < n && matrix[row][col] <= value; col++) {
            count++;
        }
    }

    return count;
}

// Faster version, used above: walk from the top-right corner, where left
// means smaller and down means bigger. A cell at or below value means the
// whole row up to it is too, so count it and step down. Otherwise step
// left. The row version without restarting each row. At most 2n steps.
function countAtMost(matrix, value) {
    const n = matrix.length;
    let row = 0;
    let col = n - 1;
    let count = 0;

    while (row < n && col >= 0) {
        if (matrix[row][col] <= value) {
            count += col + 1;
            row++;
        } else {
            col--;
        }
    }

    return count;
}

module.exports = { kthSmallest, countAtMost, countAtMostByRows };

Stack: Asking the Right Questions

Seeing it in a statement

Every problem statement has two parts. What it asks for, the shape of the answer. What it offers, the structure in the input we can lean on. The pattern is where the two meet. For a stack, what the input offers is always the same thing underneath. Some elements cannot be decided with only what has been read so far. Their answer depends on something that comes later, so they wait on the stack. When that something arrives, it decides the most recent waiting element first.

If the oldest waiting element is decided first, not the newest, it is a queue. If elements have to leave from both ends, as in Sliding Window Maximum, it is a deque, covered in Sliding Window.

Five problems follow, each read from its statement to the pattern. No code here, the code lives in Implementation and Examples.

1. Valid Parentheses

The statement. Valid Parentheses gives a string made only of the characters (, ), [, ], {, and }, and asks whether it is valid. A string is valid when every opening bracket is closed by a bracket of the same type, and brackets close in the correct order. "([]{})" is valid. "([)]" is not, since the [ is still open when ) tries to close the (.

Asks for. Whether the brackets are correctly nested.

Offers. Openers that wait for their closer, where the opener that must close next is always the latest one still open.

Why it fits. Read the string left to right. No opener can be decided yet, since its answer depends on a closer that comes later, so it waits. When a closer arrives, it can only match one opener, the most recent one still open, since anything opened after that would have to close first. In "([)]" the ) arrives while [ is the latest open bracket, so the match fails right there. The waiting openers are decided newest first, which is exactly what a stack gives. At the end, the string is valid only if nothing is left waiting.

2. Decode String

The statement. Decode String gives an encoded string and asks for it decoded. The rule is k[text], which means text repeated k times, and these can be nested inside each other. "3[a]2[bc]" decodes to "aaabcbc". "3[a2[c]]" decodes to "accaccacc", since the inner 2[c] becomes cc first, then acc is repeated three times.

Asks for. A nested structure expanded.

Offers. An inner part that must be finished before the part around it can continue.

Why it fits. When a [ arrives, the text built so far and the repeat count in front of the bracket cannot be used yet, they wait until the matching ]. Inside, another [ can start, and that inner part has to finish first. So the outer parts pile up, each waiting on the one inside it. When a ] arrives, it closes the innermost part, which was the latest one started, and its result is joined onto the part saved just before it. The newest waiting part is decided first, so a stack holds the saved outer state.

3. Asteroid Collision

The statement. Asteroid Collision gives an array of integers representing asteroids in a row. The absolute value is the asteroid’s size, and the sign is its direction, positive moving right and negative moving left. All move at the same speed. When two meet, the smaller one explodes, and if they are the same size, both explode. Two moving in the same direction never meet. It asks for the asteroids left after all collisions. [5, 10, -5] becomes [5, 10], since -5 meets 10 and explodes. [10, 2, -5] becomes [10], since -5 destroys 2 and is then destroyed by 10.

Asks for. What survives after all collisions.

Offers. A left-moving asteroid that only ever meets the nearest right-moving asteroid in front of it, the most recent survivor.

Why it fits. Read left to right, keeping the survivors so far. A right-moving asteroid cannot collide with anything yet, so it waits. A left-moving asteroid travels back through the survivors and meets the most recent one first. If it wins, that survivor is gone and it meets the next most recent one. If it loses or ties, it stops. Collisions always happen with the newest survivor, which is the top of a stack. Two pointers do not fit, since one arrival can remove any number of earlier asteroids, and they are always removed newest first.

4. Daily Temperatures

The statement. Daily Temperatures gives an array of daily temperatures and asks, for each day, how many days later the next warmer day comes. If no warmer day comes, the answer for that day is 0. For [73, 74, 75, 71, 69, 72, 76, 73], the answer is [1, 1, 4, 2, 1, 1, 0, 0].

Asks for. For each element, the next greater element to its right.

Offers. Days that wait for a warmer day, where a new warm day decides the colder waiting days starting from the most recent.

Why it fits. The plain approach looks forward from every day for a warmer one. Instead, read left to right and let days wait. In the example, 75 waits, then 71 waits, then 69 waits. When 72 arrives, it is warmer than 69, the most recent waiting day, so 69 is decided, with an answer of 1. Then it is warmer than 71, which is decided with 2. It is not warmer than 75, so 75 keeps waiting, and 72 joins the waiting days.

The waiting days are always in falling order of temperature, from the oldest to the newest, because a warmer arrival decides every colder day before it waits. So the newest waiting day is always the coldest, and it is the first one any new day can decide. The stack stays in order without ever being sorted, which is why this form is called a monotonic stack.

5. Largest Rectangle in Histogram

The statement. Largest Rectangle in Histogram gives an array of bar heights, each bar 1 wide and standing next to each other, and asks for the area of the largest rectangle that fits inside the bars. For [2, 1, 5, 6, 2, 3], the answer is 10, from the bars 5 and 6, height 5 and width 2.

Asks for. The widest range where a bar is the shortest, times that bar’s height, at its best.

Offers. For each bar, a range that stretches until the nearest shorter bar on each side.

Why it fits. The largest rectangle has some bar as its shortest bar, using that bar’s full height. Stretched as far as it can go, it ends just before the nearest shorter bar on the left and the nearest shorter bar on the right. So every bar needs its two nearest shorter neighbors, a next smaller question in both directions.

Read left to right and let bars wait for their right end. When a shorter bar arrives, it ends every taller waiting bar, the most recent first. The bars still waiting are in rising order of height, so the bar just below an ended bar in the stack is the nearest shorter bar on its left. One arrival gives the right end and the bar beneath gives the left end, and the rectangle for that bar is its height times the gap between the two. In the example, when 2 arrives at index 4, it ends 6, with left end 5 at index 2, area 6. Then it ends 5, with left end 1 at index 1, area 5 times 2, which is 10.

What the five share

In every one, some elements cannot be decided with only what has been read so far, because their answer depends on something that comes later. An opener waits for its closer, an outer part waits for its inner part, a right-moving asteroid waits for a collision, a day waits for a warmer day, a bar waits for a shorter one. And in every one, a new arrival decides the waiting elements newest first, stopping at the first one it cannot decide. Once decided, an element is never needed again. That newest-first order is what a stack provides. When the oldest waiting element is the one to decide first, the problem calls for a queue instead.

Implementation

JavaScript has no separate stack type. A plain array is the stack, with push adding to the top, pop removing from the top, and the last element being the top.

const stack = [];
stack.push(x);
const top = stack[stack.length - 1];
stack.pop();

Both push and pop work at the end of the array, so neither moves any other element. The pattern lives in two decisions, what goes on the stack, and when an arriving element decides the one on top.

One loop underlies every stack problem. Read the elements left to right. For each one, first let it decide whatever it can on top of the stack, popping each element it decides, newest first. Then, if it cannot be decided yet itself, push it to wait.

Matching

Openers wait for their closer. A closer can only match the opener on top, the most recent one still open.

function isValid(s) {
    const opener = { ')': '(', ']': '[', '}': '{' };
    const stack = [];

    for (const ch of s) {
        if (!(ch in opener)) {
            stack.push(ch);
        } else if (stack.pop() !== opener[ch]) {
            return false;
        }
    }

    return stack.length === 0;
}

A closer that meets an empty stack, or the wrong opener on top, fails right there. An opener still waiting at the end never got its closer, so the stack has to be empty for the string to be valid. Cancellation problems use the same shape. An arriving element meets the element on top, and either one or both are removed, until it stops or the stack runs out.

Saving the outer state

When parts nest inside each other, what waits is not a single element but the work done so far on the outer part. Opening a new part pushes that work, and closing the part pops it and joins the inner result onto it.

function decodeString(s) {
    const stack = [];
    let current = '';
    let count = 0;

    for (const ch of s) {
        if (ch >= '0' && ch <= '9') {
            count = count * 10 + Number(ch);
        } else if (ch === '[') {
            stack.push([current, count]);
            current = '';
            count = 0;
        } else if (ch === ']') {
            const [outer, repeat] = stack.pop();
            current = outer + current.repeat(repeat);
        } else {
            current += ch;
        }
    }

    return current;
}

current is always the innermost part being built. The stack holds every outer part waiting on it, the most recently opened one on top, which is the one a ] closes.

Monotonic stack

Each element waits for the next element that is greater, or smaller, than it. The stack holds indices, not values, since the answer is usually a position or a distance, and the index gives both the position and, through the array, the value.

function nextGreater(nums) {
    const answer = new Array(nums.length).fill(-1);
    const stack = [];

    for (let i = 0; i < nums.length; i++) {
        while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
            const waiting = stack.pop();
            answer[waiting] = i;
        }
        stack.push(i);
    }

    return answer;
}

answer[waiting] is the index of the next greater element. For a distance, as in Daily Temperatures, store i - waiting instead. Elements still on the stack at the end never found a greater element, so their answer stays at the default.

The while is where the stack stays in order. Every element smaller than the arrival gets decided and popped before the arrival is pushed, so the waiting values only fall from bottom to top. That is why the top is the first one any arrival can decide, and why the loop can stop at the first element it cannot decide.

Four variations come from the same loop.

For the previous ones, the answer for i is whatever sits on top after the popping, before i is pushed. When values repeat, whether the comparison is strict decides whether an equal value counts as greater or smaller, so it is worth checking against the statement.

The one thing that actually matters

The loop is the same every time, decide what the arrival can decide, newest first, then push the arrival if it has to wait. What changes between problems is what waits on the stack, a bracket, a saved outer part, or an index, and what it means for an arrival to decide the element on top, a matching closer, a closing bracket, or a greater or smaller value. Once those two are named, the code follows.

Stack: Examples

Worked problems, reasoning and code together, one shape at a time.

Matching and Nesting

Minimum Remove to Make Valid Parentheses gives a string s of (, ), and lowercase letters, and asks for as few parentheses as possible to be removed so that the rest is valid. Valid means every ( has a later ) closing it, and every ) closes an earlier (. Any valid result can be returned. "lee(t(c)o)de)" becomes "lee(t(c)o)de", "a)b(c)d" becomes "ab(c)d", and "))((" becomes "".

Asks for. A cleaned string, not a yes or no.

Offers. Openers that wait for a closer, where the latest open one is the one a closer matches, the same as in Valid Parentheses.

The first idea is to run Valid Parentheses and look at what is left on the stack. That finds part of the answer. Valid Parentheses can stop at the first problem it meets, but here every bad bracket has to be found, and they come in two kinds that show up at different times.

A ) that arrives while the stack is empty has nothing to close. It is bad the moment it arrives, and since it never goes on the stack, the leftover stack will never show it. It has to be marked for removal right then. In "a)b(c)d", the ) at index 1 is the one to remove, and the stack ends empty.

A ( that is still on the stack when the string ends never got its closer. It is bad too, but that is only known at the end.

To remove a leftover (, we need its position, not just the fact that one is left. So the stack holds indices instead of characters. At the end, every index still on the stack joins the marked ones, and the string is rebuilt without any marked index.

Take "lee(t(c)o)de)".

i    char  action                  stack
3    (     push 3                  3
5    (     push 5                  3 5
7    )     pop 5                   3
9    )     pop 3                   empty
12   )     nothing open, mark 12   empty
end        nothing left to mark
remove {12}, the result is "lee(t(c)o)de"

In "))((", indices 0 and 1 are marked as they arrive, and 2 and 3 are left on the stack, so all four go and the result is "".

This removes as few as possible. Every bracket removed had no partner at all, and every matched pair is kept, so no removed bracket could have been saved.

// Minimum Remove to Make Valid Parentheses
// https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/
//
// Problem: s has '(', ')' and lowercase letters. Remove as few parentheses
// as possible so the result is valid, and return any valid result.
//
// Match brackets as in Valid Parentheses, but keep indices so the bad
// ones can be removed. A ')' with nothing open is bad the moment it
// arrives. A '(' still on the stack at the end never got closed.

function minRemoveToMakeValid(s) {
    const stack = [];
    const remove = new Set();

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else if (s[i] === ')') {
            if (stack.length > 0) {
                stack.pop();
            } else {
                remove.add(i);
            }
        }
    }

    for (const i of stack) {
        remove.add(i);
    }

    let result = '';
    for (let i = 0; i < s.length; i++) {
        if (!remove.has(i)) result += s[i];
    }

    return result;
}

module.exports = { minRemoveToMakeValid };

Asteroid Collision gives an array of integers, one per asteroid in a row. The absolute value is the asteroid’s size, and the sign is its direction, positive moving right and negative moving left. All move at the same speed. When two meet, the smaller one explodes, and if they are the same size, both explode. Two moving in the same direction never meet. It asks for the asteroids left after all collisions. [5, 10, -5] becomes [5, 10], [8, -8] becomes [], [10, 2, -5] becomes [10], and [-2, -1, 1, 2] stays as it is, since nothing meets.

Asks for. What survives.

Offers. An arriving asteroid that only ever meets the most recent survivor first.

For a right-moving asteroid to be in the final answer, it has to be bigger than every left-moving asteroid that reaches it. A right-moving asteroid cannot be decided when it is read, since its fate depends on left-moving asteroids that come later. So it waits on the stack. The stack holds the survivors so far, and right-moving asteroids are always pushed.

The work happens when a left-moving asteroid arrives. It travels back through the survivors and meets the top first, the most recent one. As long as the top is right-moving, there are three outcomes, and the comparison is between sizes, the top against the arrival’s absolute value.

Only the first case keeps going. If the arrival destroys every right-moving asteroid on top and reaches an empty stack, or a top that is also moving left, nothing can reach it any more, and it is pushed. That is why left-moving asteroids at the start, as in [-2, -1, 1, 2], survive. Nothing right-moving comes before them.

Take [10, 2, -5].

read  action                              stack
10    moving right, push                  10
2     moving right, push                  10 2
-5    top 2 is smaller, pop it            10
      top 10 is bigger, -5 explodes       10
result [10]

In one line, right-moving asteroids are always pushed, and a left-moving one pops smaller right-moving asteroids off the top, then either dies on one at least its size, or is pushed once nothing moving right is left on top.

// Asteroid Collision
// https://leetcode.com/problems/asteroid-collision/description/
//
// Problem: each integer is an asteroid, its absolute value the size and
// its sign the direction, positive moving right and negative moving left.
// When two meet, the smaller explodes, and equal sizes both explode.
// Return the asteroids left after all collisions.
//
// The stack holds the survivors so far. A right-moving asteroid cannot
// hit anything yet, so it is pushed. A left-moving one meets the most
// recent survivor first, the top, and keeps going while it wins.

function asteroidCollision(asteroids) {
    const stack = [];

    for (const a of asteroids) {
        if (a > 0) {
            stack.push(a);
            continue;
        }

        // Smaller right-moving asteroids on top explode.
        while (stack.length > 0 && stack[stack.length - 1] > 0 && stack[stack.length - 1] < -a) {
            stack.pop();
        }

        if (stack.length > 0 && stack[stack.length - 1] === -a) {
            // Same size, both explode.
            stack.pop();
        } else if (stack.length === 0 || stack[stack.length - 1] < 0) {
            // Nothing moving right is left to hit it.
            stack.push(a);
        }
        // Otherwise a bigger right-moving asteroid is on top, and a explodes.
    }

    return stack;
}

module.exports = { asteroidCollision };

Simplify Path gives an absolute Unix path, starting with /, and asks for its simplified form. A . means the current directory and does nothing. A .. means go up one directory, and at the root it stays at the root. Several slashes in a row count as one. Any other name is a directory, including .... The result starts with /, has single slashes between names, no trailing slash, and no . or ... "/home//foo/" becomes "/home/foo", "/../" becomes "/", and "/.../a/../b/c/../d/./" becomes "/.../b/d".

Asks for. A cleaned path.

Offers. A .. that removes the most recent directory still in the path, a cancellation like the asteroids.

The stack holds directory names. Each name is pushed as it is read, and a .. pops the most recent one, the directory it leaves. At the end, the names still on the stack are the path, joined with / and with a / in front.

Splitting the path on / gives the pieces, but it also gives empty ones. "/home//foo/".split("/") is ["", "home", "", "foo", ""], an empty piece for the leading slash, one for the double slash, and one for the trailing slash. They are skipped the same way as .. A .. at the root finds the stack empty, and since there is nothing above the root, it does nothing.

Take "/home/user/Documents/../../Pictures/../".

piece      action   stack
""         skip
home       push     home
user       push     home user
Documents  push     home user Documents
..         pop      home user
..         pop      home
Pictures   push     home Pictures
..         pop      home
""         skip     home
result "/home"

An empty stack at the end gives "/" + "", which is "/", so the root needs no special case.

// Simplify Path
// https://leetcode.com/problems/simplify-path/description/
//
// Problem: given an absolute Unix path, return its simplified form. "."
// does nothing, ".." goes up one directory (staying at the root if
// already there), repeated slashes count as one, and any other name,
// including "...", is a directory.
//
// The stack holds the directory names still in the path. A ".." cancels
// the most recent one, the top.

function simplifyPath(path) {
    const stack = [];

    for (const piece of path.split('/')) {
        if (piece === '' || piece === '.') {
            continue;
        }

        if (piece === '..') {
            if (stack.length > 0) stack.pop();
        } else {
            stack.push(piece);
        }
    }

    return '/' + stack.join('/');
}

module.exports = { simplifyPath };

Monotonic Stack

A monotonic stack is a stack whose values, from bottom to top, always run in one direction, all falling or all rising. Nothing sorts it. Before a new value is pushed, every value on top that would break the order is popped, so the order holds when it lands. And it does not hold every element, only the ones that can still be someone’s answer. The popped ones are gone for good.

Online Stock Span gives prices one day at a time through a call next(price). Each call returns that day’s span, the number of consecutive days, counting back from today and including today, whose price was at or below today’s price. For prices [100, 80, 60, 70, 60, 75, 85], the spans are [1, 1, 1, 2, 1, 4, 6]. The 75 covers itself, 60, 70, and 60, and stops at 80.

Asks for. For each day, how far back it reaches before a bigger price stops it, the previous greater element.

Offers. Prices that arrive one at a time, with nothing known about the days to come.

Compare each new price with the last element of the stack, and pop until that element is greater than the new price. Whatever is left on top is the previous greater day, where the span stops. Popping is safe. When 75 arrives, the days 60, 70, and 60 are covered, and any later day that reaches back past 75 reaches past them too. No later day will ever stop at them, so they never need to be looked at again.

The stack holds indices, the day numbers, and the span comes from them. Today’s span runs from the day after the previous greater day up to today, so it is today - top. If the stack is empty, no earlier day was greater, and the span reaches all the way back to day 0, which is today + 1. Since prices arrive through calls instead of as an array, the prices seen so far are kept in an array of their own, so the stack’s indices can be looked up.

day  price  pops            top left  span        stack (prices)
0    100                    none      0 + 1 = 1   100
1    80                     0         1 - 0 = 1   100 80
2    60                     1         2 - 1 = 1   100 80 60
3    70     day 2 (60)      1         3 - 1 = 2   100 80 70
4    60                     3         4 - 3 = 1   100 80 70 60
5    75     days 4, 3       1         5 - 1 = 4   100 80 75
6    85     days 5, 1       0         6 - 0 = 6   100 85

Every row of the stack is falling from bottom to top, and no sort ever ran.

// Online Stock Span
// https://leetcode.com/problems/online-stock-span/description/
//
// Problem: prices arrive one day at a time through next(price). Each call
// returns the span, the number of consecutive days back from today,
// today included, whose price was at or below today's price.
//
// The span ends at the previous day with a greater price. The stack holds
// the indices of days still waiting to be that day for someone, in
// falling price order. Days at or below today's price are popped, since
// any later day that reaches past today reaches past them too.

class StockSpanner {
    constructor() {
        this.prices = [];
        this.stack = [];
    }

    next(price) {
        const today = this.prices.length;
        this.prices.push(price);

        while (this.stack.length > 0 && this.prices[this.stack[this.stack.length - 1]] <= price) {
            this.stack.pop();
        }

        const span = this.stack.length > 0
            ? today - this.stack[this.stack.length - 1]
            : today + 1;

        this.stack.push(today);
        return span;
    }
}

module.exports = { StockSpanner };

Remove K Digits gives a string num of digits and a number k, and asks for exactly k digits to be removed so that the remaining number is as small as possible, with the remaining digits kept in their original order. The result is returned as a string with no leading zeros, or "0" if nothing is left. "1432219" with k = 3 becomes "1219", "10200" with k = 1 becomes "200", and "10" with k = 2 becomes "0".

Asks for. The smallest number after removing k digits.

Offers. Digits in a fixed order, where a digit further left matters more than every digit after it.

Nothing in the statement says “next greater” or “previous smaller”, so the stack is not in the wording. It comes from the goal. The final number has n - k digits, so there are n - k positions to fill, and each one should hold the smallest digit it can. Filling them from the left matters most, since a smaller digit in an earlier position beats anything after it, 1999 is smaller than 2000.

One way to fill the positions is to pick, for each one, the smallest digit within reach. A position can only reach so far ahead, since enough digits have to be left to fill the positions after it. In "1432219" with k = 3 there are four positions, and the first can choose from 1 4 3 2, so it takes 1. That works, but it scans the same digits again for every position.

The stack reaches the same result in one pass. It builds the answer as it reads, and corrects it when a better digit arrives. If the new digit is smaller than the digit on top, and removals are left, the top was a worse choice for its position. It is popped, one removal is used, and the new top is checked the same way. Otherwise the new digit is pushed. Each pop gives an earlier position a smaller digit.

digit  action                      k left  stack
1      push                        3       1
4      push                        3       1 4
3      4 is bigger, pop it         2       1
       push 3                      2       1 3
2      3 is bigger, pop it         1       1
       push 2                      1       1 2
2      equal, push                 1       1 2 2
1      2 is bigger, pop it         0       1 2
       no removals left, push      0       1 2 1
9      push                        0       1 2 1 9
result "1219"

The stack never ends up too short. Each pop uses one removal, and pops stop when k reaches 0, so at most k digits go and at least n - k remain. The reach limit from the first idea is built into the counter.

It can end up too long. If removals are left over at the end, as in "12345" with k = 2, where no digit is ever smaller than the one before it, the stack holds more than n - k digits. The extra ones come off the end. If removals were left over, no pop was ever stopped for lack of removals, so the stack never goes down from bottom to top, and its largest digits are at the end. "12345" keeps its first three, "123".

The last step is leading zeros. "10200" with k = 1 pops the 1 when the 0 arrives and leaves "0200", which is stripped to "200". If nothing is left after stripping, the answer is "0".

// Remove K Digits
// https://leetcode.com/problems/remove-k-digits/description/
//
// Problem: num is a string of digits. Remove exactly k digits, keeping
// the rest in order, so the remaining number is as small as possible.
// Return it with no leading zeros, or "0" if nothing is left.
//
// The answer has n - k positions, and each should hold the smallest digit
// it can. The stack builds the answer left to right. A smaller digit
// arriving means the digit on top was a worse choice for its position, so
// it is popped, while removals are left.

function removeKdigits(num, k) {
    const keep = num.length - k;
    const stack = [];

    for (const digit of num) {
        while (k > 0 && stack.length > 0 && stack[stack.length - 1] > digit) {
            stack.pop();
            k--;
        }
        stack.push(digit);
    }

    // Removals left over: the stack never went down, so its largest
    // digits are at the end.
    const result = stack.slice(0, keep).join('').replace(/^0+/, '');

    return result === '' ? '0' : result;
}

module.exports = { removeKdigits };

Sum of Subarray Minimums gives an array arr and asks for the minimum of every contiguous subarray, all added up, returned modulo 10^9 + 7. For [3, 1, 2, 4] the answer is 17.

Asks for. A sum over every subarray, about n² / 2 of them.

Offers. A minimum that, once a smaller element arrives, stops mattering for every subarray that reaches past that smaller element.

There are several ways to group the same subarrays, and each one leads further. The first groups them by length.

length 1: [3] [1] [2] [4]          mins 3 1 2 4   = 10
length 2: [3,1] [1,2] [2,4]        mins 1 1 2     = 4
length 3: [3,1,2] [1,2,4]          mins 1 1       = 2
length 4: [3,1,2,4]                min 1          = 1
total 17

The second groups them by where they start, which lets one running minimum serve a whole row instead of recomputing each subarray.

start at 3: [3] [3,1] [3,1,2] [3,1,2,4]   mins 3 1 1 1   = 6
start at 1: [1] [1,2] [1,2,4]             mins 1 1 1     = 3
start at 2: [2] [2,4]                     mins 2 2       = 4
start at 4: [4]                           min 4          = 4
total 17

Both still visit every subarray. The third view walks left to right and asks what each new element changes. The first element is 3. Then 1 arrives, and 1 is smaller than 3, so in any subarray from here on that contains both, 1 is the minimum, never 3. The 3 is still the minimum of [3], but for every subarray ending later that reaches past 1, it no longer matters, and it can be dropped. Then 2 arrives. It does not beat 1, but it is the minimum of the short subarrays that start after 1, the ones where 1 is missed, so it stays.

That points at grouping by where subarrays end. Let endSum[j] be the sum of minimums of all subarrays ending at j, and the answer is all the endSum values added up. When arr[j] arrives, pop every element on the stack at or above it, those are the “1 beats 3” cases, and the element left on top is the previous smaller one, at index p. That splits the subarrays ending at j in two.

The ones that start after p contain only elements at or above arr[j], so their minimum is arr[j], and there are j - p of them. The ones that start at or before p contain arr[p], which is smaller than everything between p and j, so adding those elements changes nothing, and their minimums are exactly the minimums of the subarrays ending at p. Those are already summed in endSum[p].

endSum[j] = endSum[p] + arr[j] × (j - p)

If the stack is empty, there is no smaller element before j, p is -1, and the first term is 0.

j  arr  pops  p   endSum                  subarrays ending at j      total
0  3          -1  3 × 1 = 3               [3]                        3
1  1    3     -1  1 × 2 = 2               [3,1] [1]                  5
2  2          1   endSum[1] + 2 × 1 = 4   [3,1,2] [1,2] [2]          9
3  4          2   endSum[2] + 4 × 1 = 8   [3,1,2,4] [1,2,4] [2,4] [4] 17

At j = 3, endSum[2] = 4 already covers [3,1,2,4], [1,2,4], and [2,4], with minimums 1, 1, and 2, and 4 × 1 adds [4]. The stack rises from bottom to top, and only the previous smaller element is ever needed. Under the problem’s limits, at most 3 × 10^4 elements each at most 3 × 10^4, adding arr[j] × (j - p) keeps every number below 2 × 10^9 before the modulo, so plain numbers are safe.

// Sum of Subarray Minimums
// https://leetcode.com/problems/sum-of-subarray-minimums/description/
//
// Problem: add up the minimum of every contiguous subarray of arr, and
// return the sum modulo 10^9 + 7.
//
// Group subarrays by where they end. endSum[j] is the sum of minimums of
// all subarrays ending at j. Let p be the previous smaller element. The
// subarrays starting after p have minimum arr[j], and the ones starting
// at or before p have the same minimums as the subarrays ending at p.

function sumSubarrayMins(arr) {
    const MOD = 1_000_000_007;
    const endSum = new Array(arr.length).fill(0);
    const stack = [];
    let total = 0;

    for (let j = 0; j < arr.length; j++) {
        // A smaller arrival takes over every subarray that reaches past it.
        while (stack.length > 0 && arr[stack[stack.length - 1]] >= arr[j]) {
            stack.pop();
        }

        const p = stack.length > 0 ? stack[stack.length - 1] : -1;
        const before = p >= 0 ? endSum[p] : 0;

        endSum[j] = (before + arr[j] * (j - p)) % MOD;
        total = (total + endSum[j]) % MOD;

        stack.push(j);
    }

    return total;
}

module.exports = { sumSubarrayMins };

Practice: Name the Pattern

Each problem below is stated without any hint of the pattern that solves it. Read the statement, decide what it asks for and what it offers, and name the pattern before opening the reveal.

1. Brick Wall

Brick Wall gives a wall made of rows of bricks. Every row has the same total width, and wall[i] lists the widths of the bricks in row i, from left to right. Draw one vertical line from the top of the wall to the bottom. Where the line passes through a brick, it crosses that brick, and where it runs along the edge between two bricks, it crosses nothing in that row. The line cannot be drawn along the wall’s left or right edge. Return the fewest bricks the line can cross.

For this wall the answer is 2.

wall = [[1, 2, 2, 1],
        [3, 1, 2],
        [1, 3, 2],
        [2, 4],
        [3, 1, 2],
        [1, 3, 1, 1]]

row 0: 1, 3, 5
row 1: 3, 4
row 2: 1, 4
row 3: 2
row 4: 3, 4
row 5: 1, 4, 5

// Brick Wall
// https://leetcode.com/problems/brick-wall/description/
//
// Problem: each row of the wall lists brick widths, and every row has the
// same total width. Draw a vertical line, not along the outer edges, that
// crosses the fewest bricks, and return that number.
//
// A row's edges sit at the running sums of its widths. Count how many rows
// have an edge at each position, leaving out the right edge. The line goes
// where the count is highest, and crosses every other row.

function leastBricks(wall) {
    const edges = new Map();
    let most = 0;

    for (const row of wall) {
        let position = 0;

        // The last brick ends at the wall's right edge, which is not allowed.
        for (let i = 0; i < row.length - 1; i++) {
            position += row[i];
            const count = (edges.get(position) || 0) + 1;
            edges.set(position, count);
            most = Math.max(most, count);
        }
    }

    return wall.length - most;
}

module.exports = { leastBricks };

2. Car Fleet

Car Fleet gives n cars on a one-lane road, all driving toward a destination at mile target. position[i] is car i’s starting mile and speed[i] its speed in miles per hour, and no two cars start at the same mile. A car can never pass the car ahead of it. When a faster car catches up to a slower one, it slows down and the two drive together from then on at the slower speed, as a fleet. A car that catches up exactly at the destination still joins that fleet. A single car on its own also counts as a fleet. Return the number of fleets that arrive at the destination.

For target = 12, position = [10, 8, 0, 5, 3], and speed = [2, 4, 1, 1, 3], the answer is 3. The cars at 10 and 8 meet at mile 12 and arrive together. The car at 0 arrives alone. The cars at 5 and 3 meet at mile 6 and arrive together.