mafeshsho8lmafeshsho8l
Get Started
All coding questions

House Robber

medium
Blind 75NeetCode 150dynamic-programming

Problem

Given the amounts of money in a row of houses, find the maximum you can rob without taking from two adjacent houses, since adjacent robberies trigger the alarm.

Examples

Input: nums = [1, 2, 3, 1]
Output: 4
Rob houses 1 and 3 for 1 + 3 = 4.
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Rob houses with 2, 9, and 1.

Constraints

  • • 1 <= nums.length <= 100
  • • 0 <= nums[i] <= 400
Hints(tap to reveal)
  • 1. At each house choose to skip or rob plus two back.
  • 2. Carry forward two running best totals.
Optimal approach(spoiler)
  1. Track the best total including the current house and excluding it.
  2. Robbing the current house adds its value to the prior excluded best.
  3. Skipping keeps the prior overall best.
  4. Slide these two values across the row.
  5. O(n) time, O(1) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor