Loading…

mediumStack QueueSometimes asked

Equal Stacks

Q: How do you solve Equal Stacks using the Brute Force — Chop the Tallest, Re-sum Each Time approach?

When to use it: Say this first to show you understand the mechanics, then point out the repeated re-summing as the thing to fix. The mechanics are simple: keep popping the top of the tallest stack until all three totals are equal. This version computes heights the lazy way — by walking a stack and adding up its cylinders whenever it needs a height. **Why only the tallest is worth touching.** Heights only ever decrease. If two stacks are at 9 and 7, popping the 7 can only push it further below 9, never toward it. The single move that can bring the group closer to a common value is to lower the current maximum. So at every step you scan for the tallest and pop exactly that one. **Why it terminates.** Every pop strictly reduces the sum of all three heights by at least one (cylinder heights are positive). The sum can't drop below 0, and the all-empty state (height 0) is always equal, so the loop must end. **Where the waste is.** Re-deriving a stack's height by re-summing its cylinders is pure repeated work. The height changes by exactly the popped cylinder's value — you already know that value. Tracking a running total instead of re-summing is the entire fix, and it drops the cost to one linear pass. Time complexity: O((n1+n2+n3) · maxHeight). Space complexity: O(1) beyond the stacks.

Q: How do you solve Equal Stacks using the Suffix Sums + Lockstep Reduction (Optimal) approach?

When to use it: The answer they want. Phrase it as 'precompute each stack's reachable heights, then walk all three down together'. Read each stack top-to-bottom and keep an index pointing at its current top, plus a running total. Sum each stack once up front. Then loop: if the three totals are equal, return; otherwise subtract the top cylinder of whichever stack has the largest total and advance that stack's top pointer. **The reframing that makes it fast.** A stack's possible heights are exactly its suffix sums from the top — a strictly decreasing list. So instead of searching, you maintain three running totals and only ever move them downward. The popped cylinder's height is the exact amount each total drops, so the update is O(1); there's never a reason to re-sum. **Why shrinking the tallest is the safe greedy.** Suppose the answer — the largest common reachable height — is H. Every total is ≥ H until it reaches it (totals only decrease and start at the full heights ≥ H). If a total is strictly above H, it still has cylinders to drop, so popping its top can't skip past H illegally for the *tallest*: the tallest is the furthest from agreement and must come down. Lowering anything but the maximum can't create equality, so the maximum is always the right thing to reduce. **Why each cylinder is touched once.** A pointer only moves down a stack, never back up. So across the whole run, the number of pops is at most the total cylinder count — that's the linear bound. Contrast with the brute force, which re-summed surviving cylinders again and again. **The set-intersection view.** Equivalently, build the suffix-sum *set* for each stack and return the maximum value present in all three. The lockstep reduction is just that intersection computed in a single descending sweep without materialising the sets — same idea, less memory. Time complexity: O(n1 + n2 + n3). Space complexity: O(1) extra.

Stack & Queue · 10 of 17 · 8 min

You are given three stacks of cylinders, each cylinder having a positive integer height. The stacks are described top-to-bottom (the first number in each array is the cylinder currently on top).

In one operation you may remove the cylinder on the top of any stack. Find the maximum possible height such that all three stacks have exactly that total height after some removals. A height of 0 (all stacks emptied) is always achievable, so an answer always exists.

Return that maximum equal height.

In plain English

Each stack can only shrink, and only from its top. The set of total heights a stack can take is exactly its suffix sums read from the top: full height, full minus the top cylinder, and so on down to 0. You want the largest value present in all three of those sets.

Examples

Example 1

Input: h1 = [3, 2, 1, 1, 1], h2 = [4, 3, 2], h3 = [1, 1, 4, 1]
Output: 5
Note: Totals start at 8, 9, 7. Trim the tallest each step until all read 5: stack1 keeps [3,2]=5, stack2 keeps [4,3]... actually 4+3=7, pop to [4,3,2]→ remove 2 leaves... the lockstep reduction lands every stack on 5.

Example 2

Input: h1 = [1, 1, 1], h2 = [1, 1], h3 = [1]
Output: 1
Note: Totals 3, 2, 1. The shortest is already 1, so the others shrink down to 1. Common reachable height is 1.

Example 3

Input: h1 = [5], h2 = [3, 2], h3 = [4, 1]
Output: 5
Note: Totals 5, 5, 5 — already equal, no removals needed.

Constraints

0 ≤ n1, n2, n3 ≤ 10⁵ (number of cylinders in each stack)
1 ≤ cylinder height ≤ 100
Input lists are given top-to-bottom: index 0 is the top cylinder
An empty stack contributes height 0

Clarifying questions4First question: Are the stacks given top-to-bottom or bottom-to-top?Explore questions

Q1.Are the stacks given top-to-bottom or bottom-to-top?
Top-to-bottom here: index 0 is the top. This matters because you remove from the top, so the order decides which cylinder leaves first.
Q2.Can heights be zero or negative?
Heights are positive. That keeps the running totals strictly decreasing as you pop, which is exactly what makes the greedy 'shrink the tallest' correct.
Q3.Is a height of 0 a valid answer?
Yes. Emptying all three stacks gives equal height 0, so the problem always has an answer — no need for a 'not possible' branch.
Q4.Do I need to return which cylinders remain, or just the height?
Just the maximum equal height. If they wanted the remaining cylinders you'd track counts alongside the sums.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

You have three stacks of cylinders and may only remove cylinders from the top. Find the maximum equal height all three can reach. The brute force repeatedly chops the tallest stack one cylinder at a time, O(n·maxHeight). The clean answer turns each stack into the set of heights reachable from its top (its suffix sums), then walks the three stacks down in lockstep from the top, dropping from whichever is currently tallest until all three totals match — O(n) total.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise reducing the tallest stack is the only move that can help, and whether you avoid re-summing stacks inside the loop.

Where candidates slip

Reading cylinders bottom-up so 'top' is mis-identified, or recomputing each stack's height from scratch every iteration, turning an O(n) walk into O(n²).

How to stand out

Frame the answer as suffix sums: each stack's reachable heights are its running totals from the top. Then either intersect three sets or lockstep-reduce. State why shrinking the tallest is safe — heights only ever decrease.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Chop the Tallest, Re-sum Each Time	`O((n1+n2+n3) · maxHeight)`	`O(1) beyond the stacks`	Say this first to show you understand the mechanics, then point out the repeated re-summing as the thing to fix.	Read
2	Suffix Sums + Lockstep Reduction (Optimal)Optimal	`O(n1 + n2 + n3)`	`O(1) extra`	The answer they want. Phrase it as 'precompute each stack's reachable heights, then walk all three down together'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewThree running totals h1, h2, h3All three equal?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Chop the Tallest, Re-sum Each Time

TimeO((n1+n2+n3) · maxHeight)SpaceO(1) beyond the stacks

Say this first to show you understand the mechanics, then point out the repeated re-summing as the thing to fix.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only legal move is to pop the top of some stack. Which stack is it ever worth popping? A stack that is already the shortest can't get shorter usefully — popping it moves away from the others.

2Hint 2Explore hint

Repeatedly: compute each stack's current height, pop the top of whichever is tallest, and stop when all three heights match.

3Hint 3Explore hint

If you re-add every cylinder in a stack to get its height on every iteration, you're doing O(n) work per pop. Spot that waste.

A · Core idea

The mechanics are simple: keep popping the top of the tallest stack until all three totals are equal. This version computes heights the lazy way — by walking a stack and adding up its cylinders whenever it needs a height.

Why only the tallest is worth touching. Heights only ever decrease. If two stacks are at 9 and 7, popping the 7 can only push it further below 9, never toward it. The single move that can bring the group closer to a common value is to lower the current maximum. So at every step you scan for the tallest and pop exactly that one.

Why it terminates. Every pop strictly reduces the sum of all three heights by at least one (cylinder heights are positive). The sum can't drop below 0, and the all-empty state (height 0) is always equal, so the loop must end.

Where the waste is. Re-deriving a stack's height by re-summing its cylinders is pure repeated work. The height changes by exactly the popped cylinder's value — you already know that value. Tracking a running total instead of re-summing is the entire fix, and it drops the cost to one linear pass.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

h1 = [1, 2, 1, 1] (top=1), h2 = [1, 1, 2], h3 = [1, 1]

Array state

start

totals 5, 4, 2 — stack1 tallest

tallest ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultall equal to 2

C · Code with teaching comments

Reference implementation previewimport java.util.*; public class Solution { public static int equalStacks(int[] h1, int[] h2, int[] h3) { Deque<Integer> s1 = build(h1);Explore the full code

solution.javaJava

Brute Force — Chop the Tallest, Re-sum Each Time — reference

4 teaching notes

1
import java.util.*;
2
 
3
public class Solution {
4
    public static int equalStacks(int[] h1, int[] h2, int[] h3) {
5
        Deque<Integer> s1 = build(h1);
6
        Deque<Integer> s2 = build(h2);
7
        Deque<Integer> s3 = build(h3);
8
        while (true) {
9
            // Re-summing every stack every iteration is the O(n)-per-step waste the
10
            // optimal version removes.
11
            int t1 = sum(s1), t2 = sum(s2), t3 = sum(s3);
12
            // All three totals match — that common value is the answer.
13
            if (t1 == t2 && t2 == t3) return t1;
14
            // Only the tallest is worth shrinking, so find it.
15
            int max = Math.max(t1, Math.max(t2, t3));
16
            // Pop a single cylinder off whichever stack is currently tallest.
17
            if (t1 == max && !s1.isEmpty()) s1.pop();
18
            else if (t2 == max && !s2.isEmpty()) s2.pop();
19
            else if (!s3.isEmpty()) s3.pop();
20
            else return 0;
21
        }
22
    }
23
 
24
    private static Deque<Integer> build(int[] arr) {
25
        Deque<Integer> st = new ArrayDeque<>();
26
        for (int i = arr.length - 1; i >= 0; i--) st.push(arr[i]);
27
        return st;
28
    }
29
 
30
    private static int sum(Deque<Integer> st) {
31
        int total = 0;
32
        for (int v : st) total += v;
33
        return total;
34
    }
35
 
36
    public static void main(String[] args) {
37
        System.out.println(equalStacks(
38
            new int[]{3, 2, 1, 1, 1},
39
            new int[]{4, 3, 2},
40
            new int[]{1, 1, 4, 1}));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO((n1+n2+n3) · maxHeight) timeO(1) beyond the stacks spaceOpen the invariant and proofExplore the proof

The greedy choice — always shrink the tallest — is correct because heights are monotonically non-increasing. Recognising that frees you from any search; the only inefficiency left is recomputing heights you could have updated incrementally.

ComplexityO((n1+n2+n3) · maxHeight) time, O(1) beyond the stacks space — Each pop removes one cylinder, so there are at most n1+n2+n3 pops. If you recompute a stack's height by summing all its cylinders each step, a single iteration costs up to O(maxStackSize), giving the product bound. The number of pops alone is linear; the re-summing is what inflates it.

E · Edge cases and pitfalls3Re-summing a whole stack on every iteration — O(n) per pop instead of O(1).Explore edge cases

Pitfalls

Re-summing a whole stack on every iteration — O(n) per pop instead of O(1).
Using list.pop(0) in Python, which is itself O(n) — pop from the end of a reversed list instead.
Popping the shortest stack — it can never rise to meet the others.

03.2

Approach 2 of 2 · Optimal

Suffix Sums + Lockstep Reduction (Optimal)

TimeO(n1 + n2 + n3)SpaceO(1) extra

The answer they want. Phrase it as 'precompute each stack's reachable heights, then walk all three down together'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What heights can a single stack actually take? Only its suffix sums from the top: the full height, then minus the top cylinder, and so on. That's a fixed, sorted-descending set.

2Hint 2Explore hint

Keep a running total per stack instead of re-summing. When you pop the top, subtract just that cylinder's height from the total.

3Hint 3Explore hint

Repeatedly subtract the top of whichever total is largest. Because totals only decrease, each cylinder is removed at most once — one linear pass.

A · Core idea

Read each stack top-to-bottom and keep an index pointing at its current top, plus a running total. Sum each stack once up front. Then loop: if the three totals are equal, return; otherwise subtract the top cylinder of whichever stack has the largest total and advance that stack's top pointer.

The reframing that makes it fast. A stack's possible heights are exactly its suffix sums from the top — a strictly decreasing list. So instead of searching, you maintain three running totals and only ever move them downward. The popped cylinder's height is the exact amount each total drops, so the update is O(1); there's never a reason to re-sum.

Why shrinking the tallest is the safe greedy. Suppose the answer — the largest common reachable height — is H. Every total is ≥ H until it reaches it (totals only decrease and start at the full heights ≥ H). If a total is strictly above H, it still has cylinders to drop, so popping its top can't skip past H illegally for the tallest: the tallest is the furthest from agreement and must come down. Lowering anything but the maximum can't create equality, so the maximum is always the right thing to reduce.

Why each cylinder is touched once. A pointer only moves down a stack, never back up. So across the whole run, the number of pops is at most the total cylinder count — that's the linear bound. Contrast with the brute force, which re-summed surviving cylinders again and again.

The set-intersection view. Equivalently, build the suffix-sum set for each stack and return the maximum value present in all three. The lockstep reduction is just that intersection computed in a single descending sweep without materialising the sets — same idea, less memory.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

h1 = [3, 2, 1, 1, 1], h2 = [4, 3, 2], h3 = [1, 1, 4, 1]

Array state

start

t2=9 tallest → advance j over the 4

j ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result5

C · Code with teaching comments

solution.javaJava

Suffix Sums + Lockstep Reduction (Optimal) — optimal

4 teaching notes

1
public class Solution {
2
    public static int equalStacks(int[] h1, int[] h2, int[] h3) {
3
        // One pass to get the starting heights — the only summing you ever do.
4
        long t1 = total(h1), t2 = total(h2), t3 = total(h3);
5
        int i = 0, j = 0, k = 0;
6
        while (true) {
7
            // All three totals agree: that's the maximum common reachable height.
8
            if (t1 == t2 && t2 == t3) return (int) t1;
9
            if (t1 >= t2 && t1 >= t3) {
10
                // Stack emptied with no match yet: the only common height left is 0.
11
                if (i == h1.length) return 0;
12
                // Pop the top cylinder by subtracting it and advancing the index —
13
                // O(1), no re-sum.
14
                t1 -= h1[i++];
15
            } else if (t2 >= t1 && t2 >= t3) {
16
                if (j == h2.length) return 0;
17
                t2 -= h2[j++];
18
            } else {
19
                if (k == h3.length) return 0;
20
                t3 -= h3[k++];
21
            }
22
        }
23
    }
24
 
25
    private static long total(int[] arr) {
26
        long s = 0;
27
        for (int v : arr) s += v;
28
        return s;
29
    }
30
 
31
    public static void main(String[] args) {
32
        System.out.println(equalStacks(
33
            new int[]{3, 2, 1, 1, 1},
34
            new int[]{4, 3, 2},
35
            new int[]{1, 1, 4, 1}));
36
    }
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n1 + n2 + n3) timeO(1) extra spaceOpen the invariant and proofExplore the proof

Reading the problem as 'the reachable heights are the suffix sums' converts an awkward simulation into either a set intersection or a monotone three-way merge. The reusable trick: when an operation can only chip away from one end, the achievable totals are prefix/suffix sums — make them explicit and the search disappears.

ComplexityO(n1 + n2 + n3) time, O(1) extra space — Computing the three initial totals is one pass over all cylinders. After that, every step pops exactly one cylinder and updates a total in O(1). A cylinder is never re-added, so the total number of pops is bounded by n1+n2+n3. Both phases are linear, so the whole thing is O(n1+n2+n3) time and O(1) extra space.

E · Edge cases and pitfalls6one stack empty, e.g. h3 = [] — t3 starts at 0; the others must shrink to 0 to match, so the answer is 0.Explore edge cases

Edge cases handled

one stack empty, e.g. h3 = []t3 starts at 0; the others must shrink to 0 to match, so the answer is 0.
all totals already equalThe first equality check returns immediately with no pops.
all stacks identicalEqual from the start — returns the full common height.

Pitfalls

Re-summing inside the loop instead of subtracting only the popped cylinder.
Reducing a non-maximal stack — wastes pops and can skip past the true answer for the tallest.
Returning before checking emptiness, or never returning 0 when a stack runs out.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic class Solution { public static int equalStacks(int[] h1, int[] h2, int[] h3) { long t1 = total(h1), t2 = total(h2), t3 = total(h3); int i = 0, j = 0, k = 0; while (true) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Re-summing the stack every step

The height changes by exactly the popped cylinder. Re-adding every surviving cylinder makes each step O(n) and the whole thing O(n²).

Explore the code comparison

Don't write this

while True:
    t1 = sum(s1)  # full re-sum each loop
    t2 = sum(s2)
    t3 = sum(s3)
    ...

Write this instead

t1, t2, t3 = sum(h1), sum(h2), sum(h3)  # once
while True:
    ...
    t1 -= h1[i]; i += 1  # O(1) update

Popping from the wrong end

The arrays are top-to-bottom, so the top is index 0. Removing from the end takes off the bottom cylinder, which you are not allowed to do.

Explore the code comparison

Don't write this

s1.pop()       # removes the BOTTOM (last) element

Write this instead

t1 -= h1[i]    # advance an index from the top (front)
i += 1

Reducing the shortest stack

Only lowering the current maximum can move the three totals toward agreement; lowering the minimum pushes it further away and burns pops.

Explore the code comparison

Don't write this

int min = Math.min(t1, Math.min(t2, t3));
if (t1 == min) t1 -= h1[i++];  // wrong direction

Write this instead

int max = Math.max(t1, Math.max(t2, t3));
if (t1 == max) t1 -= h1[i++];  // shrink the tallest

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reachable heights from the top = suffix sums; intersect / lockstep-reduce the three

Code pattern to memorize

h1 = sum(stack1); h2 = sum(stack2); h3 = sum(stack3)
while not (h1 == h2 == h3):
    pick the largest of h1,h2,h3
    subtract its top cylinder from that height (pop it)
return h1  # all equal now

Rules to remember

1You can only remove from the top — that's the cylinder nearest the input's front, not its end.
2Reduce the currently tallest stack each step; never the shortest. Reducing the short one can never bring it up to meet the others.
3An empty stack means a final equal height of 0 — that's always achievable, so an answer always exists.
4Pop only one cylinder per step from the tallest; popping more can overshoot below a height all three could have shared.
5Pre-sum each stack once, then maintain running totals — don't re-sum the whole stack every step.

Use this pattern when

Several sequences, you may only trim from one end, and you want a common total
The question is 'largest value all of them can agree on by removing from the top'
Suffix / prefix sums turn 'remove k from the end' into a membership test on a set of totals
A greedy 'shrink the biggest' loop is provably safe because heights only decrease

Choose another pattern when

You may remove from **either** end → this top-only greedy no longer holds
You need the actual cylinders kept, not just the height → track indices too
Values can be negative → suffix sums aren't monotonic, the greedy breaks
Only one stack → there's nothing to equalise

Interview takeaway

When you may only peel items off one end and want a shared total, the totals you can reach are exactly the suffix sums. Either intersect those sets or walk the stacks down together, always shrinking the tallest. Monotonic shrinking is what makes the greedy correct.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternSuffix-sum reachability with a monotone greedy. Recognise it when an operation only peels from one end and you want a common total: the achievable totals are prefix/suffix sums, and 'always shrink the largest' is safe because totals only decrease. Same shape as merging sorted descending sets and k-way greedy reductions.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two stacks instead of three
Coming soon
Same lockstep reduction with only two running totals — even simpler greedy.
k stacks, generalised
Coming soon
Use a max-heap of (total, index) and pop the tallest each step; or intersect k suffix-sum sets.
Remove from either end
Coming soon
Top-only greedy breaks; reachable totals become contiguous ranges, not suffix sums.
Maximum equal height tracking which cylinders remain
Coming soon
Carry the surviving index alongside each total so you can report the kept cylinders.

Same pattern

←

Queue Using Two Stacks

Continue · Next problem

Largest Rectangle in Histogram

mediumStack QueueSometimes asked

Equal Stacks

Stack & Queue · 10 of 17 · 8 min

You are given three stacks of cylinders, each cylinder having a positive integer height. The stacks are described top-to-bottom (the first number in each array is the cylinder currently on top).

Return that maximum equal height.

In plain English

Examples

Example 1

Input: h1 = [3, 2, 1, 1, 1], h2 = [4, 3, 2], h3 = [1, 1, 4, 1]
Output: 5
Note: Totals start at 8, 9, 7. Trim the tallest each step until all read 5: stack1 keeps [3,2]=5, stack2 keeps [4,3]... actually 4+3=7, pop to [4,3,2]→ remove 2 leaves... the lockstep reduction lands every stack on 5.

Example 2

Input: h1 = [1, 1, 1], h2 = [1, 1], h3 = [1]
Output: 1
Note: Totals 3, 2, 1. The shortest is already 1, so the others shrink down to 1. Common reachable height is 1.

Example 3

Input: h1 = [5], h2 = [3, 2], h3 = [4, 1]
Output: 5
Note: Totals 5, 5, 5 — already equal, no removals needed.

Constraints

0 ≤ n1, n2, n3 ≤ 10⁵ (number of cylinders in each stack)
1 ≤ cylinder height ≤ 100
Input lists are given top-to-bottom: index 0 is the top cylinder
An empty stack contributes height 0

Clarifying questions4First question: Are the stacks given top-to-bottom or bottom-to-top?Explore questions

Q1.Are the stacks given top-to-bottom or bottom-to-top?
Top-to-bottom here: index 0 is the top. This matters because you remove from the top, so the order decides which cylinder leaves first.
Q2.Can heights be zero or negative?
Heights are positive. That keeps the running totals strictly decreasing as you pop, which is exactly what makes the greedy 'shrink the tallest' correct.
Q3.Is a height of 0 a valid answer?
Yes. Emptying all three stacks gives equal height 0, so the problem always has an answer — no need for a 'not possible' branch.
Q4.Do I need to return which cylinders remain, or just the height?
Just the maximum equal height. If they wanted the remaining cylinders you'd track counts alongside the sums.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise reducing the tallest stack is the only move that can help, and whether you avoid re-summing stacks inside the loop.

Where candidates slip

Reading cylinders bottom-up so 'top' is mis-identified, or recomputing each stack's height from scratch every iteration, turning an O(n) walk into O(n²).

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Chop the Tallest, Re-sum Each Time	`O((n1+n2+n3) · maxHeight)`	`O(1) beyond the stacks`	Say this first to show you understand the mechanics, then point out the repeated re-summing as the thing to fix.	Read
2	Suffix Sums + Lockstep Reduction (Optimal)Optimal	`O(n1 + n2 + n3)`	`O(1) extra`	The answer they want. Phrase it as 'precompute each stack's reachable heights, then walk all three down together'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Chop the Tallest, Re-sum Each Time

TimeO((n1+n2+n3) · maxHeight)SpaceO(1) beyond the stacks

Say this first to show you understand the mechanics, then point out the repeated re-summing as the thing to fix.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The only legal move is to pop the top of some stack. Which stack is it ever worth popping? A stack that is already the shortest can't get shorter usefully — popping it moves away from the others.

2Hint 2Explore hint

Repeatedly: compute each stack's current height, pop the top of whichever is tallest, and stop when all three heights match.

3Hint 3Explore hint

If you re-add every cylinder in a stack to get its height on every iteration, you're doing O(n) work per pop. Spot that waste.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

h1 = [1, 2, 1, 1] (top=1), h2 = [1, 1, 2], h3 = [1, 1]

Array state

start

totals 5, 4, 2 — stack1 tallest

tallest ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultall equal to 2

C · Code with teaching comments

Reference implementation previewimport java.util.*; public class Solution { public static int equalStacks(int[] h1, int[] h2, int[] h3) { Deque<Integer> s1 = build(h1);Explore the full code

solution.javaJava

Brute Force — Chop the Tallest, Re-sum Each Time — reference

4 teaching notes

1
import java.util.*;
2
 
3
public class Solution {
4
    public static int equalStacks(int[] h1, int[] h2, int[] h3) {
5
        Deque<Integer> s1 = build(h1);
6
        Deque<Integer> s2 = build(h2);
7
        Deque<Integer> s3 = build(h3);
8
        while (true) {
9
            // Re-summing every stack every iteration is the O(n)-per-step waste the
10
            // optimal version removes.
11
            int t1 = sum(s1), t2 = sum(s2), t3 = sum(s3);
12
            // All three totals match — that common value is the answer.
13
            if (t1 == t2 && t2 == t3) return t1;
14
            // Only the tallest is worth shrinking, so find it.
15
            int max = Math.max(t1, Math.max(t2, t3));
16
            // Pop a single cylinder off whichever stack is currently tallest.
17
            if (t1 == max && !s1.isEmpty()) s1.pop();
18
            else if (t2 == max && !s2.isEmpty()) s2.pop();
19
            else if (!s3.isEmpty()) s3.pop();
20
            else return 0;
21
        }
22
    }
23
 
24
    private static Deque<Integer> build(int[] arr) {
25
        Deque<Integer> st = new ArrayDeque<>();
26
        for (int i = arr.length - 1; i >= 0; i--) st.push(arr[i]);
27
        return st;
28
    }
29
 
30
    private static int sum(Deque<Integer> st) {
31
        int total = 0;
32
        for (int v : st) total += v;
33
        return total;
34
    }
35
 
36
    public static void main(String[] args) {
37
        System.out.println(equalStacks(
38
            new int[]{3, 2, 1, 1, 1},
39
            new int[]{4, 3, 2},
40
            new int[]{1, 1, 4, 1}));
41
    }
42
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.42 lines

D · Why it works and complexityO((n1+n2+n3) · maxHeight) timeO(1) beyond the stacks spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Re-summing a whole stack on every iteration — O(n) per pop instead of O(1).Explore edge cases

Pitfalls

Re-summing a whole stack on every iteration — O(n) per pop instead of O(1).
Using list.pop(0) in Python, which is itself O(n) — pop from the end of a reversed list instead.
Popping the shortest stack — it can never rise to meet the others.

03.2

Approach 2 of 2 · Optimal

Suffix Sums + Lockstep Reduction (Optimal)

TimeO(n1 + n2 + n3)SpaceO(1) extra

The answer they want. Phrase it as 'precompute each stack's reachable heights, then walk all three down together'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What heights can a single stack actually take? Only its suffix sums from the top: the full height, then minus the top cylinder, and so on. That's a fixed, sorted-descending set.

2Hint 2Explore hint

Keep a running total per stack instead of re-summing. When you pop the top, subtract just that cylinder's height from the total.

3Hint 3Explore hint

Repeatedly subtract the top of whichever total is largest. Because totals only decrease, each cylinder is removed at most once — one linear pass.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

h1 = [3, 2, 1, 1, 1], h2 = [4, 3, 2], h3 = [1, 1, 4, 1]

Array state

start

t2=9 tallest → advance j over the 4

j ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result5

C · Code with teaching comments

solution.javaJava

Suffix Sums + Lockstep Reduction (Optimal) — optimal

4 teaching notes

1
public class Solution {
2
    public static int equalStacks(int[] h1, int[] h2, int[] h3) {
3
        // One pass to get the starting heights — the only summing you ever do.
4
        long t1 = total(h1), t2 = total(h2), t3 = total(h3);
5
        int i = 0, j = 0, k = 0;
6
        while (true) {
7
            // All three totals agree: that's the maximum common reachable height.
8
            if (t1 == t2 && t2 == t3) return (int) t1;
9
            if (t1 >= t2 && t1 >= t3) {
10
                // Stack emptied with no match yet: the only common height left is 0.
11
                if (i == h1.length) return 0;
12
                // Pop the top cylinder by subtracting it and advancing the index —
13
                // O(1), no re-sum.
14
                t1 -= h1[i++];
15
            } else if (t2 >= t1 && t2 >= t3) {
16
                if (j == h2.length) return 0;
17
                t2 -= h2[j++];
18
            } else {
19
                if (k == h3.length) return 0;
20
                t3 -= h3[k++];
21
            }
22
        }
23
    }
24
 
25
    private static long total(int[] arr) {
26
        long s = 0;
27
        for (int v : arr) s += v;
28
        return s;
29
    }
30
 
31
    public static void main(String[] args) {
32
        System.out.println(equalStacks(
33
            new int[]{3, 2, 1, 1, 1},
34
            new int[]{4, 3, 2},
35
            new int[]{1, 1, 4, 1}));
36
    }
37
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.37 lines

D · Why it works and complexityO(n1 + n2 + n3) timeO(1) extra spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6one stack empty, e.g. h3 = [] — t3 starts at 0; the others must shrink to 0 to match, so the answer is 0.Explore edge cases

Edge cases handled

one stack empty, e.g. h3 = []t3 starts at 0; the others must shrink to 0 to match, so the answer is 0.
all totals already equalThe first equality check returns immediately with no pops.
all stacks identicalEqual from the start — returns the full common height.

Pitfalls

Re-summing inside the loop instead of subtracting only the popped cylinder.
Reducing a non-maximal stack — wastes pops and can skip past the true answer for the tallest.
Returning before checking emptiness, or never returning 0 when a stack runs out.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Re-summing the stack every step

The height changes by exactly the popped cylinder. Re-adding every surviving cylinder makes each step O(n) and the whole thing O(n²).

Explore the code comparison

Don't write this

while True:
    t1 = sum(s1)  # full re-sum each loop
    t2 = sum(s2)
    t3 = sum(s3)
    ...

Write this instead

t1, t2, t3 = sum(h1), sum(h2), sum(h3)  # once
while True:
    ...
    t1 -= h1[i]; i += 1  # O(1) update

Popping from the wrong end

The arrays are top-to-bottom, so the top is index 0. Removing from the end takes off the bottom cylinder, which you are not allowed to do.

Explore the code comparison

Don't write this

s1.pop()       # removes the BOTTOM (last) element

Write this instead

t1 -= h1[i]    # advance an index from the top (front)
i += 1

Reducing the shortest stack

Only lowering the current maximum can move the three totals toward agreement; lowering the minimum pushes it further away and burns pops.

Explore the code comparison

Don't write this

int min = Math.min(t1, Math.min(t2, t3));
if (t1 == min) t1 -= h1[i++];  // wrong direction

Write this instead

int max = Math.max(t1, Math.max(t2, t3));
if (t1 == max) t1 -= h1[i++];  // shrink the tallest

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reachable heights from the top = suffix sums; intersect / lockstep-reduce the three

Code pattern to memorize

h1 = sum(stack1); h2 = sum(stack2); h3 = sum(stack3)
while not (h1 == h2 == h3):
    pick the largest of h1,h2,h3
    subtract its top cylinder from that height (pop it)
return h1  # all equal now

Rules to remember

1You can only remove from the top — that's the cylinder nearest the input's front, not its end.
2Reduce the currently tallest stack each step; never the shortest. Reducing the short one can never bring it up to meet the others.
3An empty stack means a final equal height of 0 — that's always achievable, so an answer always exists.
4Pop only one cylinder per step from the tallest; popping more can overshoot below a height all three could have shared.
5Pre-sum each stack once, then maintain running totals — don't re-sum the whole stack every step.

Use this pattern when

Several sequences, you may only trim from one end, and you want a common total
The question is 'largest value all of them can agree on by removing from the top'
Suffix / prefix sums turn 'remove k from the end' into a membership test on a set of totals
A greedy 'shrink the biggest' loop is provably safe because heights only decrease

Choose another pattern when

You may remove from **either** end → this top-only greedy no longer holds
You need the actual cylinders kept, not just the height → track indices too
Values can be negative → suffix sums aren't monotonic, the greedy breaks
Only one stack → there's nothing to equalise

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Two stacks instead of three
Coming soon
Same lockstep reduction with only two running totals — even simpler greedy.
k stacks, generalised
Coming soon
Use a max-heap of (total, index) and pop the tallest each step; or intersect k suffix-sum sets.
Remove from either end
Coming soon
Top-only greedy breaks; reachable totals become contiguous ranges, not suffix sums.
Maximum equal height tracking which cylinders remain
Coming soon
Carry the surviving index alongside each total so you can report the kept cylinders.

Same pattern

←

Queue Using Two Stacks

Continue · Next problem

Largest Rectangle in Histogram