Space Optimization with Rolling Arrays
You'll learn how to reduce memory usage in dynamic programming by keeping only the essential rows or columns of your DP table instead of storing the entire matrix.
The Core Idea
Many DP solutions build a 2D table where each cell depends only on values from the previous row or previous column—not the entire history. Since older rows become irrelevant once you've moved past them, you can discard them! A rolling array keeps just 1-2 rows (or columns) in memory at a time, "rolling" through the computation while reusing the same space.
Think of it like a painter working on a mural one horizontal strip at a time. Once the current strip is done and the next strip only needs to reference the one just completed, there's no need to keep scaffolding for the very first strip anymore—you roll your workspace forward.
How It Works
- Identify the dependency: Does row
ionly depend on rowi-1? Or do two rows suffice? - Allocate minimal space: Instead of
dp[n][m], usedp[2][m]or justdp[m]. - Update in place or alternate: Either overwrite the array carefully, or toggle between two small arrays (e.g.,
currentandprevious).
For example, in the Climbing Stairs problem, you only need the last two values, not the entire history. In Longest Common Subsequence, each row depends only on the row above it, so two 1D arrays suffice.
When to Use It
Use rolling arrays when:
- Your DP table is 2D but dependencies are local (previous row/column only).
- Memory is a constraint or you want O(min(m,n)) space instead of O(m×n).
Key Takeaway: Rolling arrays shrink 2D DP space to O(1) or O(n) by keeping only the necessary previous state, sacrificing the ability to trace back through the entire table but preserving the final answer.