How do you approach House Robber II?

Since houses are in a circle, house 0 and house n-1 are adjacent.

What is the time complexity of House Robber II?

Time complexity: O(n). Space complexity: O(1).

What are common mistakes on House Robber II?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

House Robber II

MediumAlgorithms

Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are **arranged in a circle**. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**. Given an integer array `nums` representing the amount of money of each house, return the maximum amount of money you can rob tonight **without alerting the police**.

Example 1

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent.

Example 2

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

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 3

Input: nums = [1,2,3]

Output: 3

Constraints

- 1 <= nums.length <= 100 - 0 <= nums[i] <= 1000

House Robber II: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Since houses are in a circle, house 0 and house n-1 are adjacent.
You can break this into two subproblems: rob houses 0 to n-2, or rob houses 1 to n-1.
Use the House Robber I solution on each subarray and take the maximum.

The optimal approach

Show the approach: Two Passes of House Robber I

Since the first and last houses are adjacent in a circle, we can't rob both. Run House Robber I on two subarrays: houses[0..n-2] and houses[1..n-1]. The answer is the maximum of the two.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

House Robber II

MediumAlgorithms

Description

Example 1

Input: nums = [2,3,2]

Output: 3

Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent.

Example 2

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

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 3

Input: nums = [1,2,3]

Output: 3

Constraints

- 1 <= nums.length <= 100 - 0 <= nums[i] <= 1000

House Robber II: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Since houses are in a circle, house 0 and house n-1 are adjacent.
You can break this into two subproblems: rob houses 0 to n-2, or rob houses 1 to n-1.
Use the House Robber I solution on each subarray and take the maximum.

The optimal approach

Show the approach: Two Passes of House Robber I

Since the first and last houses are adjacent in a circle, we can't rob both. Run House Robber I on two subarrays: houses[0..n-2] and houses[1..n-1]. The answer is the maximum of the two.

Time: O(n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.