Space-Optimized Knapsack
Collapse 2D to a single row.
Space-Optimized Knapsack is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Why Optimize Space
A full table costs n times cap memory, which can explode on big inputs. Space optimization shrinks that to a single row you reuse.
Only the Last Row Matters
Notice each cell reads only the previous row, never anything older. So you never actually need to store the whole grid at once.
Collapse to One Array
Keep one dp array of length cap+1. As you process each item, you overwrite it in place to represent the new row.
dp = [0] * (cap + 1)The Reuse Trap
If you sweep capacity left to right, dp[w - wt[i]] may already be updated for this same item. That would let you take item i twice.
Iterate Capacity Backward
The fix is to loop capacity from high to low. Going backward guarantees dp[w - wt[i]] still holds last item's value.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Why Backward Works
When you compute dp[w], the smaller index w - wt[i] is still untouched this round, so it reflects the row above as intended.
Stop Early at the Weight
Capacities below wt[i] cannot fit the item, so the loop stops at wt[i]. Skipping them saves a few harmless cycles.
The Full Loop
The whole solution is two nested loops over one array. Items outside, capacity backward inside, and the answer falls out.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Read the Final Cell
After all items, dp[cap] holds the maximum value. It is the same number the 2D table would give, with far less memory.
Same Time, Less Memory
You did not speed up the algorithm; it is still order n times cap work. You only cut memory from quadratic to linear.
When It Pays Off
This trick rescues you when cap is large and the 2D grid would blow the memory limit. It is a contest staple worth memorizing.
Quick Check
Test the key rule for 1D knapsack.
Recap
You collapsed the 2D table into one array and looped capacity backward to stay correct, trading quadratic memory for linear. 🚀
Frequently asked questions
Is the “Space-Optimized Knapsack” lesson free?
Yes — the full text of “Space-Optimized Knapsack” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Space-Optimized Knapsack”?
Collapse 2D to a single row. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Space-Optimized Knapsack” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- 0/1 Knapsack: Take or Leave
- Space-Optimized Knapsack
- Unbounded & Coin-Change DP
- Subset Sum & Partition