Saving memory with rolling rows

Dynamic programming Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
weights, cap = [2], 4
up = [True] + [False] * cap
for w in weights:
    for t in range(w, cap + 1):
        up[t] = up[t] or up[t - w]
down = [True] + [False] * cap
for w in weights:
    for t in range(cap, w - 1, -1):
        down[t] = down[t] or down[t - w]
print(up[4], down[4])

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True False

Right: the upward sweep used the single weight 2 twice to reach 4.

Fill direction is what separates 'unlimited copies' from 'each item once' when the table is a single row.

Why not the others?
  • B False False. Upward sweeps read values already updated for this item.
  • C True True. Sweeping downward uses each item at most once, so 4 is not reachable.

30-second answer

If each row reads only the row before it, keep two rows (previous and current) instead of the whole table: O(columns) memory. Often one row works if you fill it in the right direction: left to right when a cell needs the new left neighbour, right to left when it needs the old value to its left (as in 0/1 knapsack). The catch is that you can no longer walk back to rebuild the answer.

Practise saying it · 30 s. No recording, just a timer

Explain rolling rows.

Say your answer out loud, then check which of these points you covered:

  • Keep previous row only
  • Direction matters
  • Path rebuild needs the table

Deep dive

1-D DPs that look back two cells need only two variables.

Direction matters: an upward sweep lets an item be reused; a downward sweep does not.

If you need the actual path, keep the full table or a separate 'choice' table.

Common mistakes

  • Sweeping in the wrong direction and reusing items by accident.
  • Dropping the table and then being asked for the path.

Senior take & follow-ups

Mention the direction rule with the knapsack example; it is a classic follow-up.

Follow-up questions

Think of your answer first, then open the hint.

  1. Why does 0/1 knapsack sweep downward?

    Show hint

    So each cell reads totals from before this item was considered.

  2. Can you rebuild a path with O(n) memory?

    Show hint

    Hirschberg's method does it for two-string tables by divide and conquer.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.