Developers

House Robber

MediumDynamic programmingGrade AAlso known as LeetCode 198

Houses stand in a row, and house i holds nums[i] units of money.

You may take the money from any set of houses, but you may not take from two houses that are next to each other. Return the largest total you can collect.

Examples

Input nums = [1, 2, 3, 1]
Output 4
Take houses 0 and 2: 1 + 3 = 4.
Input nums = [2, 7, 9, 3, 1]
Output 12
Take houses 0, 2 and 4: 2 + 9 + 1 = 12.
Input nums = [5]
Output 5

Constraints

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

Stuck? Take one hint at a time

Common mistakes
  • Greedily taking the largest house each time, which can block two better houses.
  • Using only best(i - 1) and forgetting the option of robbing house i.
  • Mishandling lists of length 1.
  • Updating both variables in the wrong order and overwriting a value you still need.
Questions an interviewer may ask next
  • The houses stand in a circle, so the first and last are neighbors. (Run it twice, once without each end.)
  • Return which houses you robbed, not just the total.
  • The houses form a binary tree and a house cannot be robbed together with its parent or children.
  • You may not rob more than k houses in total.

How often this is reported

Commonly reported across 11 of 25 tracked companies
11/25

Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.