Course contentsShow
← Computer Science
Lesson 956 of 2,87222. Dynamic ProgrammingFree lesson

Space Optimization with Rolling Arrays

Convert 2D DP tables to 1D arrays by keeping only the necessary previous rows or columns.

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

  1. Identify the dependency: Does row i only depend on row i-1? Or do two rows suffice?
  2. Allocate minimal space: Instead of dp[n][m], use dp[2][m] or just dp[m].
  3. Update in place or alternate: Either overwrite the array carefully, or toggle between two small arrays (e.g., current and previous).

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.