Space Optimization

One of the most important aspects of Dynamic Programming in interviews is optimizing Space Complexity. Often, a naive DP solution uses O(N) or O(N<sup>2</sup>) space, but we can reduce this to O(1) or O(N).

1. O(N) → O(1) (Fibonacci)

In the Fibonacci sequence, F(i) only depends on F(i-1) and F(i-2). We don’t need F(i-3), F(i-4), etc.

• Naive DP: int[] dp = new int[n+1] → Space: O(N)
• Optimized: Store only prev2 and prev1 → Space: O(1)

Interactive Visualization: Sliding Window

Watch how we only need 3 variables to compute the entire sequence.

[!TIP] Try it yourself: Click “Next Step” to see the window slide.

prev2 0

+

prev1 1

→

curr ?

Sequence: 0, 1

Code: Space Optimized Fibonacci

// Java
public int fib(int n) {
  if (n <= 1) return n;
  int prev2 = 0, prev1 = 1;

  for (int i = 2; i <= n; i++) {
    int curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

// Go
func Fib(n int) int {
  if n <= 1 {
    return n
  }
  prev2, prev1 := 0, 1

  for i := 2; i <= n; i++ {
    curr := prev1 + prev2
    prev2 = prev1
    prev1 = curr
  }
  return prev1
}

---

2. O(N*W) → O(W) (Knapsack/Subset Sum)

In 2D DP problems like Knapsack, dp[i][w] typically depends only on the previous row dp[i-1][...]. We can use a single 1D array to represent the “current” row, updating it in place.

Crucial Detail: We must iterate backwards to avoid using values from the current row that we just updated.

Code: Space Optimized Subset Sum

// Java
public boolean canPartition(int[] nums, int target) {
  boolean[] dp = new boolean[target + 1];
  dp[0] = true; // Base case

  for (int num : nums) {
    // Iterate backwards!
    for (int i = target; i >= num; i--) {
      dp[i] = dp[i] || dp[i - num];
    }
  }
  return dp[target];
}

// Go
func CanPartition(nums []int, target int) bool {
  dp := make([]bool, target+1)
  dp[0] = true

  for _, num := range nums {
    // Iterate backwards
    for i := target; i >= num; i-- {
      if dp[i-num] {
        dp[i] = true
      }
    }
  }
  return dp[target]
}

---

3. Deep Dive Strategy Lab: Space Optimization

Intuition Through Analogy

Think of this chapter like budget planning across months. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?

Answers to the Strategy Lab:

1. What is the bottleneck? The bottleneck is keeping a historical ledger of all previous states when only the immediately adjacent states interact.
2. Which constraint dominates? While computing time remains $O(N)$, storing the entire grid $O(N \cdot W)$ quickly exceeds the available RAM (memory constraint) for large inputs, causing an Out of Memory error or severe cache missing.
3. Which representation makes the bottleneck easier to eliminate? By viewing the dependency graphically (e.g. realizing dp[i] only points to dp[i-1]), you can “slide” a small 1D array window down the problem space instead of retaining the entire 2D matrix. This budget analogy strictly couples the variables to real-world memory constraints—once the month is over, you throw away the ledger and keep only the running balance.