beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: 0/1 Knapsack•Medium

0/1 Knapsack problem

Problem Intuition & Objective

Maximize value of items placed in a knapsack with weight limit W.

Time ComplexityO(n × W)
Optimal
Space ComplexityO(W)
Memory Bounds
Optimal Algorithmic Approach

2D DP optimized to 1D by iterating weights in reverse.

Core Invariants & Edge Cases

  • dp[i][w] = max value using first i items with capacity w
  • For each item: include (value[i] + dp[i-1][w-weight[i]]) or exclude (dp[i-1][w])
  • 1D DP traversing weights backwards avoids reusing the same item
Previous ProblemCoin change — minimum coins to make amountNext Problem Unique paths in a grid

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.