Back to ChallengesHouse RobberEasy 20 min

House Robber

You are a professional robber planning to rob houses along a street. Each house has a stashed amount of money. Return the maximum money you can rob tonight without alerting the police (cannot rob adjacent houses).

Examples

Input: nums = [1,2,3,1]

Output: 4

Rob house 1 (money = 1) and house 3 (money = 3). Total = 4.

Input: nums = [2,7,9,3,1]

Output: 12

Rob house 1 (money = 2), house 3 (money = 9), and house 5 (money = 1). Total = 12.

Constraints

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

Complexity Analysis

Time

O(n)

single pass to find max money.

Space

O(1)

constant storage space.

Test Cases

#1 Standard array

Input: [1,2,3,1]

Expected: 4

#2 Longer array

Input: [2,7,9,3,1]

Expected: 12

#3 No money in single house

Input: [0]

Expected: 0

#4 Rob outer houses

Input: [2,1,1,2]

Expected: 4

JavaScript

Output

Click "Run Code" to see output here...