aloalgo.comSpace Optimization for DP
Many DP problems only depend on the previous state or previous row. When that's the case, you can compress space dramatically without changing the time complexity.The Key Insight
Look at what your current state actually depends on:- If
dp[i]depends only ondp[i-1]anddp[i-2]→ use variables instead of an array - If
dp[i][j]depends only on rowi-1→ use one array instead of a 2D grid - If
dp[i][j]depends on rowi-1andi→ use two arrays and swap them
1D → O(1): Fibonacci
Fibonacci only needs the last two values. Instead of storing the full DP array, keep only what you need.Before: O(n) Space
After: O(1) Space
| Space | Time | |
|---|---|---|
| Before | O(n) | O(n) |
| After | O(1) | O(n) |
1D → O(1): House Robber
House Robber also only depends on the previous two values.Before: O(n) Space
After: O(1) Space
2D → 1D: Unique Paths
In Unique Paths, each cell only depends on the cell above and to the left. Since we process row by row, we only need to keep the previous row.Before: O(m × n) Space
After: O(n) Space
| Space | Time | |
|---|---|---|
| Before | O(m × n) | O(m × n) |
| After | O(n) | O(m × n) |
2D → 1D: Edit Distance
Edit distance is trickier becausedp[i][j] depends on three cells: dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. We need to save the diagonal value before overwriting.After: O(n) Space
2D → Two Arrays: When Order Matters
Sometimes the iteration order prevents in-place updates. In these cases, use two arrays and swap them.Optimization Checklist
- Identify dependencies: What previous states does your current state need?
- Check if full history is needed: Often only the last 1-2 rows/values matter.
- Consider iteration order: Can you update in-place, or do you need to preserve values?
- Handle diagonals carefully: Save values before overwriting if needed.
Common Space Optimizations
| Problem | Original | Optimized |
|---|---|---|
| Fibonacci | O(n) | O(1) |
| House Robber | O(n) | O(1) |
| Unique Paths | O(m × n) | O(n) |
| Edit Distance | O(m × n) | O(n) |
| LCS | O(m × n) | O(n) |
| 0/1 Knapsack | O(n × W) | O(W) |
Interview Tips
- Start with the unoptimized version: Get the logic right first, then optimize space.
- Mention the optimization: "I notice we only use the previous row, so we can reduce space to O(n)."
- Don't optimize prematurely: If time is tight, the unoptimized solution is correct and shows understanding.
- Test carefully: Space optimization can introduce subtle bugs with iteration order.
Practice Problems
Try implementing these with space optimization:- Fibonacci Number - O(1) space
- House Robber - O(1) space
- Unique Paths - O(n) space
- Edit Distance - O(n) space
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.