What is the brute force approach and complexity for House Robber II?

Walk the row with two flags: was the previous house taken, and was house 0 taken with time complexity O(2^N) and space complexity O(N).

What is the optimal approach and complexity for House Robber II?

Run House Robber on houses 0..n−2 and on 1..n−1, then keep the bigger answer with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for House Robber II?

Look for key signals in the prompt: "the houses are arranged in a circle" indicates The first and last houses are neighbours now. That is one extra link to handle, not a new problem.; "same alarm rule" indicates No two neighbours. The take-or-skip DP from House Robber stays the same.; "most money" indicates Compare the answers of the two cases, and keep the larger..

House Robber II

Medium·LeetCode #213 Pro OnlySlight Variation

LeetCode

Problem Statement

This is House Robber with one change. All the houses sit in a circle, so the first house is the neighbour of the last house. The alarm rule is the same: if you rob two neighbouring houses, the alarm goes off.

Return the most money you can take without robbing two neighbouring houses.

Input

nums, a list of whole numbers. nums[i] is the money in house i. The first and last entries are neighbours.

Output

The largest total you can rob, with no two neighbouring houses both robbed.

Example 1

Input: nums = [2, 3, 2]

Output: 3

Houses 0 and 2 are neighbours on the circle, so you cannot rob both. Rob house 1 (3) alone.

Example 2

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

Output: 4

Rob house 0 (1) and house 2 (3). Total 4.

Example 3

Input: nums = [1, 2, 3]

Output: 3

Houses 0 and 2 are neighbours on the circle. The best single choice is house 2 (3).

Example 4

Input: nums = [7]

Output: 7

There is only one house, so rob it.

Constraints

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 1000

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“the houses are arranged in a circle”

→ The first and last houses are neighbours now. That is one extra link to handle, not a new problem.

“same alarm rule”

→ No two neighbours. The take-or-skip DP from House Robber stays the same.

“most money”

→ Compare the answers of the two cases, and keep the larger.

Approach Complexity Ladder

Brute Force — take or skip, remembering whether house 0 was takenO(2^N)O(N)

Walk the row with two flags: was the previous house taken, and was house 0 taken

Better — memoize on (house, previous taken, first taken)O(N)O(N)

Remember each answer for the same house and the same two flags

Optimal — two plain rows, one without each endO(N)O(1)

Run House Robber on houses 0..n−2 and on 1..n−1, then keep the bigger answer

Brute Force Intuition

Walk the houses from left to right. At each house, take it or skip it, under two rules. No two houses in a row may both be taken. And if house 0 was taken, the last house is off-limits, because it is next to house 0 on the circle. A flag remembers whether house 0 was taken.

Recognition rule for this sub-pattern:

At each element: take it (and skip neighbours) or skip it. dp[i] = max(skip, take).

Remember this · DP — 1D Linear

Trigger

"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.

Think

If I knew the answer for every smaller prefix, how would I get the answer for i?

Key question

What does dp[i] mean in one sentence?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — 1D Linear translate into production architectures and low-level memory mechanics.

LLD Architecture