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?