Medium Problemsgridcounting

Water Overflow

Water is poured into the top glass of a triangular pyramid of identical glasses stacked n rows deep. Once a glass fills, half of any further overflow spills onward to each of the two glasses directly below it. Given the amount poured and a target glass, find how much water that glass ends up holding.

Do this lesson first: climbing stairs

Example input

a pyramid 6 rows deep, 18 glasses of water poured into the top one, and the target glass at row 5, position 1, the bottom row's second from the left

Expected output

16 units, which is 16 out of 32 and so exactly half a glass

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[r][c] is how much water ARRIVES at the glass in row r, position c, measured in units of one over 32 of a glass. Read that word again, because everything on this page turns on it. ARRIVING IS NOT HOLDING. A glass holds at most 32 units and passes the rest on, so what a glass HOLDS is min(dp[r][c], 32), and that is a different number from dp[r][c] at every glass that has filled. At a pour of 18 the table writes 116 at dp[4][2]; that glass holds 32 and has already sent 84 onward. Fifteen of the twenty-one glasses are full at that pour and the table shows the arriving number at every one of them, so this is not a corner case, it is most of the table. WHY THE ANSWER CAN STILL BE A CELL is therefore not a technicality to skip past. The statement asks what the target glass ends up HOLDING; the answer cell reads what ARRIVED there. The two agree only while that glass has not filled, and they agree on this page because the target was CHOSEN so that they would. Glass (5, 1), the bottom row's second from the left, first receives any water at all at a pour of 14, and first reaches its 32-unit capacity at a pour of 22. That is where both ends of the slider come from: it runs 14 to 21 and stops one short of the pour that would break the reading. Drag it to the maximum and the answer is 28 out of 32, close to full and not there. At a pour of 22 the cell would read 32 and be right by accident; at 23 it would read 36, and no glass holds 36 units of anything. The bottom LEFT glass, (5, 0), would have been the obvious target and is a worse one in the other direction: it is 0 at every pour below 32, which is already past the top of any range this page could show, so every answer here would be 0. It is not dry forever, and the honest bound is worth stating rather than the dramatic one: from a pour of 32 it holds exactly pour minus 31 units, and it does not itself fill until a pour of 63, so a slider running 32 to 62 would be perfectly usable. It is simply not usable HERE. If you take one sentence from this page, take this one. A table that models a quantity is not obliged to model the question, and knowing where the two stop lining up is your job and not the table's.

dp[r][c] = (max(0, dp[r-1][c-1] - 32) + max(0, dp[r-1][c] - 32)) ÷ 2, where a parent that does not exist contributes no term at all rather than a zero

THERE IS NO DECISION HERE, and that is the thing this cell has to teach. Ask where the water in this glass came from and the answer is not one of two places, it is both of them, at the same time. The glass up and to the left and the glass up and to the right each spill whatever they could not hold, each splits its spill evenly between the two glasses beneath it, and this glass sits beneath both. So the two arms are ADDED, never compared, `combine` reports op sum, and the timeline on this page shows no compare panel at any cell, because there is no choice for one to display. Hold that against the pages either side of it. min-cost-path takes a MIN over the cell above and the cell to the left, because a path arrives from one of them and you want the cheaper. min-sum-in-a-triangle does the same going downwards. maximum-tip-calculator takes a MAX over its two arms, because exactly one of the two waiters served the last customer. All three ask WHICH of two things happened, and a max or a min plus a winner is what that question costs. This page asks HOW MUCH of two things happened, and the arithmetic follows the question: a plus. The division is the second half of the rule and it is physics rather than bookkeeping. A glass that spills S does not send S to each glass below it, it sends S/2 to each. Halving the SUM of the two spills is the same number as adding the two halves, and it is one operation instead of two, which is why the narration on every cell states a single division. THE SUBTRACTION IS THE PART THAT IS EASY TO DROP. A parent's cell value is what arrived at it, so the spill is that value minus the 32 it keeps, floored at zero, and a parent that never filled contributes a real, honest 0 rather than a negative number. Use the parent's raw value in place of its spill and the pyramid stops modelling glasses at all: the water would go on being passed down whole, and the top glass would still be handing 576 units to row 1 after it had already kept 32 of them.

THERE IS EXACTLY ONE BASE, dp[0][0], and it holds the whole pour: 18 glasses at the drive size, which in units of one over 32 of a glass is 18 times 32, or 576. It is also the only place the amount poured enters the table at all. Every one of the other 20 live cells is computed, and each of them draws from the row above and from nowhere else, which is why dragging the slider never moves a dot. TWO THINGS A READER GETS WRONG HERE, and they are different mistakes. FIRST, THE DOTS. The grid is declared 6 by 6 because row 5 needs six positions, but row r holds only r + 1 glasses, so every position with col > row shows a dot. A dot is not a glass holding nothing. It is not a glass. This page is unusual in how much it would GET AWAY WITH if the dots were zeros, and that is worth measuring rather than borrowing another page's alarm. min-sum-in-a-triangle takes a min over sums, and as its own page works out, a zero above its diagonal is a free number a descent would cheat through and its answer would come out below the truth. Here a phantom position would compute max(0, 0 - 32) = 0 and contribute 0 to a sum, which is exactly what a missing arm contributes already. Measured at all eight slider sizes: fill the whole 6 by 6 rectangle, skip nothing, and let every phantom position compute from its neighbours; every one of them comes out 0 and the answer cell does not move, staying at 1, 4, 8, 12, 16, 20, 24, 28. THE MARGIN IS EXACTLY ZERO, at every phantom position and every pour, and that is a stronger statement than a cushion rather than a weaker one, because it is structural instead of numeric: the phantom region is CLOSED under this recurrence, since a position with col > row is fed only by positions with col > row, and it starts empty, since row 0 has water in position 0 alone. Zeros there can never fill and so can never spill. Be exact, then, about what the dot is doing on this page, because it is NOT propping up the answer the way it is on min-sum-in-a-triangle. It is keeping the table honest about the pyramid it is a picture of. A zero at row 2, position 4 would assert that a glass stands there, and the next reader would be right to ask what happens when it fills. SECOND, THE EDGE CELLS. Ten of the twenty computed cells have ONE parent rather than two, and the reason is positional again. A cell in column 0 has no glass up and to its left, because that would be row r - 1, position -1, and no row has a position -1: that one is off the pyramid altogether. A cell on the diagonal, where col equals row, has no glass up and to its right, because that would be row r - 1, position r, and row r - 1 stops one position short: that one is a dot inside the declared rectangle. Off the table and dot on the table is the only difference between the two cases, and neither is a parent that contributed nothing. The other ten cells have two parents. Both counts hold at every slider position, because the slider moves the POUR and not the pyramid. Measured by driving every authored problem that has a slider, this is the only one whose declared shape does not move across its own range: 6 by 6 at all eight pours. What moves inside that fixed shape was measured too, rather than assumed, and it is not everything. Of the 21 live cells, 19 hold a different value at a pour of 21 than at a pour of 14; dp[5][0] and dp[5][5] are 0 at every one of the eight pours, and dp[4][0] and dp[4][4] are 0 at the first two before they start climbing. ORDER. Row-major, left to right, and it needs one property and has it: both parents of any glass sit in the row ABOVE it, never in its own row. The previous row being finished is the whole requirement, so the order within a row is free.

Tabulation over the 21 glasses, one row-major sweep, no decision at any of them. WHY EVERY NUMBER ON THIS TABLE IS A WHOLE NUMBER is the method this page exists to show, and it is the part that transfers. Under the natural unit, the glass, the values turn fractional immediately: pour 18 glasses in and the two glasses of row 1 get (18 - 1) ÷ 2 = 8.5 each. Every step down halves again, so by row 5 the denominators have reached 2^5 = 32 and the table is a wall of thirty-seconds printed as decimals, which is exact, because these are all dyadic fractions, and unreadable, which is the actual problem. MEASURE IN UNITS OF ONE OVER 2^(rows - 1) INSTEAD, which at 6 rows is one over 32, and every value is an integer. The base becomes 18 times 32 = 576, and the deepest chain of halvings a unit of water can go through on its way to the bottom is five, which 32 absorbs exactly. NOW STATE THE MECHANISM PRECISELY, because the obvious version of it is FALSE. It is not that no overflow is ever odd. There are odd overflows on this pyramid and there are many of them; the first appears at a pour of 32, where the glass at row 5, position 1 receives 73 units and spills 41. What makes the unit work is a narrower claim: no INTERIOR glass ever has an odd overflow. The odd ones all sit in the BOTTOM row, whose spill runs onto the table the pyramid is standing on rather than into another glass, and so is never divided by anything. Nothing that gets halved is ever odd. Measured at every pour from 1 to 200: not one interior glass with an odd overflow, not one non-integer value anywhere in the table, and every odd overflow there is coming from the bottom row. Re-derive that by sweeping the pyramid in integer units at each pour and bucketing every glass's overflow by parity and by row, rather than by trusting this paragraph. The `total % 2` assertion in `problems.test.ts` now re-checks the load-bearing half of it on every run, at every slider size, against this page's own narrated arithmetic: the first time a halved total came out odd the suite would say so, instead of the page quietly printing a half. COST, and this page's cost is unusual. Constant work per glass, one subtract-and-floor per parent, then one add and one halve, so O(rows^2) time and O(rows^2) space, which is linear in the number of GLASSES and quadratic in the number of ROWS. What it is not is a function of the pour. The slider here moves the amount of water rather than the size of the pyramid, so all eight positions build the same 21-cell table and perform the same 20 divisions. The work does not move at all, and most but not all of the values do: 19 of the 21 cells differ between the two ends of the slider, and the two bottom corners are 0 throughout. Driving every authored problem with a slider, this is the only one whose declared shape is constant across its own range. A glass reads only the row above it, so two rows are enough to be live at once and the space falls to O(rows). One array of `rows` entries is enough if you sweep each row RIGHT TO LEFT, so that the entry one position to the left is still the previous row's when you reach it; sweeping left to right in place destroys it, and not subtly. Checked against the full table at every slider size: right to left reproduces the bottom row exactly, and left to right returns all zeros at a pour of 18.

Time O(rows²), constant work at each of the rows × (rows + 1) / 2 glasses, which is 21 here and does not change with the pourSpace O(rows²) for the whole pyramid, reducible to O(rows) with one array swept right to left

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

THERE IS EXACTLY ONE BASE, dp[0][0], and it holds the whole pour: 18 glasses at the drive size, which in units of one over 32 of a glass is 18 times 32, or 576. It is also the only place the amount poured enters the table at all. Every one of the other 20 live cells is computed, and each of them draws from the row above and from nowhere else, which is why dragging the slider never moves a dot. TWO THINGS A READER GETS WRONG HERE, and they are different mistakes. FIRST, THE DOTS. The grid is declared 6 by 6 because row 5 needs six positions, but row r holds only r + 1 glasses, so every position with col > row shows a dot. A dot is not a glass holding nothing. It is not a glass. This page is unusual in how much it would GET AWAY WITH if the dots were zeros, and that is worth measuring rather than borrowing another page's alarm. min-sum-in-a-triangle takes a min over sums, and as its own page works out, a zero above its diagonal is a free number a descent would cheat through and its answer would come out below the truth. Here a phantom position would compute max(0, 0 - 32) = 0 and contribute 0 to a sum, which is exactly what a missing arm contributes already. Measured at all eight slider sizes: fill the whole 6 by 6 rectangle, skip nothing, and let every phantom position compute from its neighbours; every one of them comes out 0 and the answer cell does not move, staying at 1, 4, 8, 12, 16, 20, 24, 28. THE MARGIN IS EXACTLY ZERO, at every phantom position and every pour, and that is a stronger statement than a cushion rather than a weaker one, because it is structural instead of numeric: the phantom region is CLOSED under this recurrence, since a position with col > row is fed only by positions with col > row, and it starts empty, since row 0 has water in position 0 alone. Zeros there can never fill and so can never spill. Be exact, then, about what the dot is doing on this page, because it is NOT propping up the answer the way it is on min-sum-in-a-triangle. It is keeping the table honest about the pyramid it is a picture of. A zero at row 2, position 4 would assert that a glass stands there, and the next reader would be right to ask what happens when it fills. SECOND, THE EDGE CELLS. Ten of the twenty computed cells have ONE parent rather than two, and the reason is positional again. A cell in column 0 has no glass up and to its left, because that would be row r - 1, position -1, and no row has a position -1: that one is off the pyramid altogether. A cell on the diagonal, where col equals row, has no glass up and to its right, because that would be row r - 1, position r, and row r - 1 stops one position short: that one is a dot inside the declared rectangle. Off the table and dot on the table is the only difference between the two cases, and neither is a parent that contributed nothing. The other ten cells have two parents. Both counts hold at every slider position, because the slider moves the POUR and not the pyramid. Measured by driving every authored problem that has a slider, this is the only one whose declared shape does not move across its own range: 6 by 6 at all eight pours. What moves inside that fixed shape was measured too, rather than assumed, and it is not everything. Of the 21 live cells, 19 hold a different value at a pour of 21 than at a pour of 14; dp[5][0] and dp[5][5] are 0 at every one of the eight pours, and dp[4][0] and dp[4][4] are 0 at the first two before they start climbing. ORDER. Row-major, left to right, and it needs one property and has it: both parents of any glass sit in the row ABOVE it, never in its own row. The previous row being finished is the whole requirement, so the order within a row is free.

row r: how far down the pyramid, 0 at the top glass

0

1

2

3

4

5

0

576

·

1

272

·

2

120

240

120

·

3

44

148

44

·

4

6

64

116

64

6

·

5

0

16

58

16

0

position c within that row, counted from the left

water-overflow.ts

1function arriving(pour, rows, targetRow, targetCol) {
2 const cap = 2 ** (rows - 1), dp = Array.from({ length: rows }, (_, r) => new Array(r + 1).fill(0));
3 dp[0][0] = pour * cap;
4 const spilled = (r, c) => (c < 0 || c > r ? 0 : Math.max(0, dp[r][c] - cap));
5 for (let r = 1; r < rows; r++) for (let c = 0; c <= r; c++) {
6 const passedDown = spilled(r - 1, c - 1) + spilled(r - 1, c);
7 dp[r][c] = passedDown / 2;
8 }
9 // dp holds what ARRIVES at a glass. What it HOLDS is Math.min(dp[r][c], cap).
10 return dp[targetRow][targetCol];
11}

Base caseComputedBeing readAnswer

The code, the trap, the variations

water-overflow.ts

1function arriving(pour, rows, targetRow, targetCol) {
2 const cap = 2 ** (rows - 1), dp = Array.from({ length: rows }, (_, r) => new Array(r + 1).fill(0));
3 dp[0][0] = pour * cap;
4 const spilled = (r, c) => (c < 0 || c > r ? 0 : Math.max(0, dp[r][c] - cap));
5 for (let r = 1; r < rows; r++) for (let c = 0; c <= r; c++) {
6 const passedDown = spilled(r - 1, c - 1) + spilled(r - 1, c);
7 dp[r][c] = passedDown / 2;
8 }
9 // dp holds what ARRIVES at a glass. What it HOLDS is Math.min(dp[r][c], cap).
10 return dp[targetRow][targetCol];
11}

Where people go wrong

Reporting what ARRIVED at the target glass when the question asked what it HOLDS. This is not a slip at the edge of the problem, it is the problem: a table whose cells mean one thing is being read for an answer that means another, and the two coincide over exactly the range where the target has not filled. On this page they coincide everywhere the slider goes, and that is a fact about the target glass rather than about the method. Push one step past the slider's maximum and it breaks: at a pour of 22 the cell reads 32 and is accidentally right, at 23 it reads 36 and the true answer is still 32, at 30 it reads 64 and the true answer is still 32. The fix is one line, `Math.min(dp[r][c], cap)`, and the cost of not knowing you need it is an answer that is wrong without ever looking wrong. THE SAME CONFUSION IN ITS OPERATIONAL FORM is what actually breaks people's code, and it happens one level down. When a cell reads its two parents, the numbers it gets back are ARRIVALS, not spills. There are two ways to get that wrong and one of them goes quiet at the drive size, which is the part worth knowing. Stand at the gate on dp[5][1] at a pour of 18, with 6 and 64 in front of you. DROP THE SUBTRACTION ENTIRELY and you get (6 + 64) ÷ 2 = 35 against a true 16. That one is CAUGHT, and not by you: 35 is more than the 32 units a glass holds, so the capacity bound rules it out on sight. Run the same slip through the whole table and it stays caught, giving 70, 75, 80, 85, 90, 95, 100 and 105 at pours of 14 to 21, over capacity at every one. DO THE SUBTRACTION BUT DROP THE FLOOR AT ZERO and at this pour nothing rules it out. dp[4][0] holds 6, so it contributes 6 - 32 = -26, a glass handing water back up the pyramid, and the cell computes (-26 + 32) ÷ 2 = 3. Three is whole, under capacity and entirely plausible, and the truth is 16. Through the whole table that slip gives -17, -12, -7, -2, 3, 8, 13 and 18 across the slider: obviously broken at the first four pours, where the sign gives it away, and quietly wrong at the last four. The floor is doing more work than the subtraction is, and it is the half that gets left out. THE THIRD TRAP IS TREATING THE TWO ARMS AS ALTERNATIVES, out of habit from the other ragged 2D tables in this course. min-sum-in-a-triangle in the basic tier and maximum-tip-calculator in this one both pick a winner from the row above; this one takes both. If a compare panel would help you here, the recurrence you have written down is not this problem's. THE FOURTH costs nothing at first and then costs everything: solving in glasses instead of in thirty-seconds. Nothing crashes and nothing is even inexact, because every value on this pyramid is a dyadic fraction and a double holds those exactly; the answer just arrives as 0.5 where the table said 16, and dp[4][0] as 0.1875 where it said 6. What goes is the ability to read a row at a glance, and the habit of trusting the arithmetic to be exact, which stops being earned the moment the split stops being a half. The uneven-split variation below is where that second bill comes due.

Split the overflow UNEVENLY, say two thirds to the left glass and one third to the right, because the pyramid leans.
The recurrence barely changes, one weight per arm instead of a shared half, and the WHOLE-NUMBER TRICK DIES. Measured exactly, in rationals rather than in doubles: with a two-thirds split at a pour of 18 the target glass receives 577/243 of a glass, and the denominators appearing across the table are 3, 9, 27, 81 and 243. There is no power-of-two unit that makes those integers, because the denominators are now powers of THREE, and the unit was never about halving as such, it was about the denominators all being powers of one number. Pick a dyadic split instead and the trick survives at a price: with three quarters to the left, the same pour puts 3281/1024 of a glass at the target, and the unit has to become one over 4^(rows - 1) = 1024 rather than one over 32. Note the second casualty in both cases. 3281/1024 and 577/243 are each more than one glass, so the target has FILLED, and the slider bounds this page picked would have to be measured again from scratch before the answer cell could be read as an answer.
Ask for the total that ends up on the table the pyramid stands on, rather than for one glass.
This is NOT a cell of this table and it is worth saying out loud, because the instinct is to look for one. It is a FOLD over the bottom row: sum max(0, dp[rows - 1][c] - 32) across every position c in that row. The table computes it, the table does not contain it, and no amount of choosing a better target glass would make it a cell. Measured across this page's slider, the floor takes 0, 0, 12, 32, 52, 72, 92 and 112 units at pours of 14 to 21; nothing reaches the floor at all until a pour of 16, which is the first pour that fills a bottom-row glass. It also gives you the accounting check the walkthrough uses: everything held plus everything on the floor equals the pour, so 524 + 52 = 576 at a pour of 18. The general shape of this variation recurs all over the course. When an answer is a fold over a row rather than a single cell, the table is still the right table; what changes is only the last line.
Let the target glass fill, by extending the slider past a pour of 22.
The table does not change at all, and neither does the recurrence: dp already means arriving water, and the spill it hands downward has always been max(0, arriving - 32), so the overflow of a full target glass is already modelled correctly for everything BELOW it. What changes is the last line, from `dp[r][c]` to `Math.min(dp[r][c], 32)`. That is the entire cost, and the reason it is this cheap is that the capacity was never a property of the answer cell, it was a property of every cell, applied on the way down. What is lost is the page's tidiest claim rather than its correctness: past a pour of 22 the answer is a flat 32 forever, so the slider stops showing anything, which is exactly why the range stops at 21. WHERE the answer goes flat depends on which glass you point at, and DEPTH IS NOT WHAT DECIDES IT. Measured, the first pour at which a glass reaches capacity: (5, 2) at 16, (5, 1) at 22, (4, 0) at 31, (5, 0) at 63. Moving the target one step inward along the same bottom row brings the flat point forward to 16; moving it UP to (4, 0) pushes it back to 31, later than this page's 22 rather than sooner. The pattern the measurements show runs across a row and not down the pyramid: at every row that has an interior glass at all, which is rows 2 to 5, the middle fills first and the two ends fill last. Row 2 goes 7, 5, 7 and row 5 goes 63, 22, 16, 16, 22, 63. The reason is the arity this page keeps coming back to: an interior glass is fed from both sides and an end glass is fed from one.

Longest Common Subsequence