beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: DP•Medium

House Robber — max sum of non-adjacent elements

Problem Intuition & Objective

Find the maximum sum from a sequence where no two adjacent elements can be chosen.

Time ComplexityO(n)
Optimal
Space ComplexityO(1)
Memory Bounds
Optimal Algorithmic Approach

1D DP reduced to two variables.

Core Invariants & Edge Cases

  • dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • Only need to track prev2 and prev1 (O(1) space)
  • House Robber II: handle circular array by running twice (exclude first or last)
Previous ProblemJump game — can you reach the last index?Next Problem Longest common subsequence (LCS)

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.