Knapsack: Optimizing Space to O(W)

In our last lesson, we constructed a bottom-up dynamic programming solution for the 0/1 Knapsack problem using a 2D table. This gave us the correct answer but at a space cost of O(n * W), where n is the number of items and W is the knapsack's capacity. While correct, in a coding interview or a situation with a very large number of items, this space usage can be a significant drawback.

Today, we will focus on a powerful and common optimization technique that reduces the space complexity to just O(W). This lesson is all about understanding how and, more importantly, why this optimization works. Mastering this isn't just about saving memory; it's about developing a deeper intuition for data dependencies in dynamic programming, a skill that's highly valued and applicable to many other problems.

The Key Insight: Analyzing Data Dependencies

Let's revisit the recurrence relation we derived for the 2D solution:

$$dp[i][c]=\max (dp[i-1][c],val[i-1]+dp[i-1][c-wgt[i-1]])$$

Notice a critical detail: to compute any value in the current row i, we only ever need values from the immediately preceding row, i-1. We never look back at i-2, i-3, or any earlier rows.

This observation is the gateway to our optimization. If we only need the previous row to compute the current one, why do we need to store the entire table?

A Stepping Stone: From a 2D Table to Two Rows

A straightforward improvement would be to use only two 1D arrays, let's call them prev and curr, both of size W+1. When we process item i:

1. We read values from the prev array (which holds the results for item i-1).
2. We compute the new values and store them in the curr array.
3. Once we've processed all capacities for item i, the curr array now holds the complete results for row i. We can then discard the old prev array and treat curr as the new prev for the next item, i+1.

This simple change reduces the space complexity from O(n * W) to O(2 * W), which simplifies to O(W). The take U forward video explains this two-row approach clearly as a bridge to the final optimization.

The Leap to a Single Array

Now for the main question: can we get by with just one 1D array?

Let's imagine we have a single array, dp, of size W+1. When we begin processing a new item i, this array dp holds the optimal values using items up to i-1. Our goal is to update this array in-place so that it holds the optimal values for items up to i.

The recurrence would look like this, where we want to update dp[c] for the current item:

dp[c] = max(dp[c], val[i-1] + dp[c - wgt[i-1]])

Here's the problem:

• The first dp[c] (the "don't take" option) should be the value from the previous iteration (using items up to i-1).
• The dp[c - wgt[i-1]] term (part of the "take" option) should also be the value from the previous iteration.

If we update the dp array using a standard forward loop for capacity c (from 0 to W), we run into a major issue. When we calculate dp[c], the value at dp[c - wgt[i-1]] might have already been updated in this same pass for item i. This corrupts our logic; it's like we are using item i once to get the value dp[c - wgt[i-1]] and then potentially using it again to get dp[c]. This accidentally models the Unbounded Knapsack problem, where you can take items multiple times.

So, how do we ensure we're always reading values from the previous item's state?

The Solution: Iterating Backwards

The solution is remarkably elegant: we reverse the direction of our inner loop. Instead of iterating capacity c from 0 up to W, we iterate from W down to 0 (or more precisely, down to the weight of the current item).

Why does this work?

• When we compute the new value for dp[c], we need to read the "old" value from dp[c - wgt[i-1]].
• Since we are iterating from right to left, and c - wgt[i-1] is always to the left of c, the value at dp[c - wgt[i-1]] has not yet been updated in this pass for item i.
• Therefore, dp[c - wgt[i-1]] still holds the value from the previous state (the "snapshot" before we started processing the current item). This correctly preserves the 0/1 constraint.

The following article provides a fantastic mental model for this concept.

The image below illustrates the dependencies for a single cell in the 2D table. When moving to 1D, the backward loop ensures that when you calculate the equivalent of the green cell, the dependent cell (from the previous row, to the left) hasn't been overwritten yet in the current pass.

Calculation of maxValue[1][4] depends on values from the previous row (i=0). The backward loop in the 1D optimization preserves these dependencies by ensuring maxValue[0][0] isn't overwritten before being used to calculate maxValue[1][4].

The take U forward video also has an excellent visual demonstration of this backward iteration process.

The Optimized Implementation

Here is the final, space-optimized Python code. Notice its conciseness. The outer loop iterates through items, and the critical inner loop iterates backward through capacities.

def knapsack_1d_dp(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    # 1D DP array of size capacity + 1
    dp = [0] * (capacity + 1)

    # Iterate through each item
    for i in range(n):
        w = weights[i]
        v = values[i]
        
        # Iterate backwards from capacity down to the item's weight
        # This is the crucial part for 0/1 Knapsack
        for c in range(capacity, w - 1, -1):
            # Same recurrence, but using the single 1D array
            # dp[c] here is the "don't take" value from the previous state
            # dp[c - w] is the "take" value from the previous state
            dp[c] = max(dp[c], v + dp[c - w])
            
    # The answer is the last element in the dp array
    return dp[capacity]

# Example from the previous lesson
weights = [3, 4, 5]
values = [30, 50, 60]
capacity = 8
print(knapsack_1d_dp(weights, values, capacity)) # Output: 90

The space complexity is now O(W), as we only need one array of size W+1. The time complexity remains O(n * W).

Conclusion

In this lesson, we successfully optimized the 0/1 Knapsack solution from O(n * W) space to O(W). This is a classic and essential DP optimization pattern.

Key Takeaways:

• Dependency Analysis: The optimization is possible because computing the DP state for item i only requires the state for item i-1.
• The Snapshot Problem: When updating a DP array in-place, you must ensure you are reading values from the "snapshot" of the previous state, not from the partially updated current state.
• Backward Iteration: For 0/1 Knapsack, iterating the capacity loop backwards (from W down to w) solves the snapshot problem. It guarantees that dp[c - w] holds a value from the previous item's pass.
• Pattern Recognition: The direction of this inner loop is a powerful pattern. Backward iteration implies a "use once" (0/1) constraint, while forward iteration (which we'll see later) implies a "use many times" (unbounded) constraint.

You've now seen the full development of a DP solution: from recurrence, to 2D table, to a space-optimized 1D array. In our next lesson, we'll see how this fundamental 0/1 Knapsack pattern can be adapted to solve other seemingly different problems, such as Subset Sum and Partition Equal Subset Sum.