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