House Robber II (LC 213): Circular Houses with Two Linear DP Passes

Maximize loot from houses arranged in a circle without robbing two neighbors. Since the first and last house are adjacent, run linear House Robber on houses 0..n-2 and 1..n-1 and take the larger. O(n) time, O(1) space.

Language Selection

Choose your preferred programming language

Showing: Python

House Robber II

Problem Statement

Houses on a street are arranged in a circle, so the last house is a neighbor of the first one. The array nums gives the amount of money in each house. Robbing two neighboring houses on the same night trips the alarm. Return the largest total you can collect without ever robbing two adjacent houses.

This is the House Robber problem with one extra adjacency: nums[0] and nums[n - 1].

Examples

Example 1:

Input: nums = [3,5,4]
Output: 5
Explanation: In a circle every pair of these three houses is adjacent, so you can rob only one. The best is the house with 5.

Example 2:

Input: nums = [4,1,2,7,5,3,1]
Output: 14
Explanation: Rob houses 0, 3 and 5 (4 + 7 + 3). Robbing 4 + 2 + 5 + 1 is not allowed because the first and last houses touch.

Example 3:

Input: nums = [5,1,1,5]
Output: 6
Explanation: On a straight street 5 + 5 = 10 would be best, but here the two 5s are neighbors. The best is 5 + 1 = 6.

Constraints

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

The Key Reduction

The circle only adds one restriction: you cannot rob both house 0 and house n - 1. Every valid plan therefore falls into at least one of two cases:

  1. House n - 1 is not robbed. Then the problem is ordinary linear House Robber on houses 0 .. n-2.
  2. House 0 is not robbed. Then it is linear House Robber on houses 1 .. n-1.

Each linear subproblem is a straight street with no wraparound, so the standard DP applies. The answer is the larger of the two results. The only special case is a single house (n = 1): both ranges would be empty, but the lone house is not adjacent to anything else, so the answer is nums[0].

Approach 1: Two Linear DP Passes with a Table

Algorithm

For a straight range lo .. hi, let dp[i] be the most money from the first i houses of that range. A house is either skipped (keep dp[i - 1]) or robbed (its value plus dp[i - 2]):

dp[0] = 0
dp[1] = nums[lo]
dp[i] = max(dp[i - 1], dp[i - 2] + nums[lo + i - 1])
  1. If n == 1, return nums[0].
  2. Compute the linear answer for 0 .. n-2 and for 1 .. n-1 with the table above.
  3. Return the larger one.

Implementation

Python:

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]  # a single house has no neighbor

        def rob_line(lo: int, hi: int) -> int:
            # dp[i] = best total from the first i houses of nums[lo..hi]
            length = hi - lo + 1
            dp = [0] * (length + 1)
            dp[1] = nums[lo]
            for i in range(2, length + 1):
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[lo + i - 1])
            return dp[length]

        # Either the last house is skipped or the first house is skipped
        return max(rob_line(0, n - 2), rob_line(1, n - 1))

Java:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }

    private int robLine(int[] nums, int lo, int hi) {
        // dp[i] = best total from the first i houses of nums[lo..hi]
        int length = hi - lo + 1;
        int[] dp = new int[length + 1];
        dp[1] = nums[lo];
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[lo + i - 1]);
        }
        return dp[length];
    }
}

Go:

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0] // a single house has no neighbor
    }
    // Either the last house is skipped or the first house is skipped
    return max(robLine(nums[:n-1]), robLine(nums[1:]))
}

// robLine solves House Robber on a straight street.
func robLine(houses []int) int {
    // dp[i] = best total from the first i houses
    dp := make([]int, len(houses)+1)
    dp[1] = houses[0]
    for i := 2; i <= len(houses); i++ {
        dp[i] = max(dp[i-1], dp[i-2]+houses[i-1])
    }
    return dp[len(houses)]
}

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0]; // a single house has no neighbor

    const robLine = (lo, hi) => {
        // dp[i] = best total from the first i houses of nums[lo..hi]
        const length = hi - lo + 1;
        const dp = new Array(length + 1).fill(0);
        dp[1] = nums[lo];
        for (let i = 2; i <= length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[lo + i - 1]);
        }
        return dp[length];
    };

    // Either the last house is skipped or the first house is skipped
    return Math.max(robLine(0, n - 2), robLine(1, n - 1));
};

C#:

using System;

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return Math.Max(RobLine(nums, 0, n - 2), RobLine(nums, 1, n - 1));
    }

    private int RobLine(int[] nums, int lo, int hi) {
        // dp[i] = best total from the first i houses of nums[lo..hi]
        int length = hi - lo + 1;
        int[] dp = new int[length + 1];
        dp[1] = nums[lo];
        for (int i = 2; i <= length; i++) {
            dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[lo + i - 1]);
        }
        return dp[length];
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }

private:
    int robLine(const vector<int>& nums, int lo, int hi) {
        // dp[i] = best total from the first i houses of nums[lo..hi]
        int length = hi - lo + 1;
        vector<int> dp(length + 1, 0);
        dp[1] = nums[lo];
        for (int i = 2; i <= length; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[lo + i - 1]);
        }
        return dp[length];
    }
};

Complexity Analysis

  • Time: O(n). Two passes over at most n - 1 houses each.
  • Space: O(n) for the DP table.

Approach 2: Two Passes with Rolling Variables (Optimal)

Algorithm

Each dp[i] depends only on the two previous entries, so the table can be replaced by two variables:

  • prev2: best total up to two houses back.
  • prev1: best total up to the previous house.

For each house in the range, current = max(prev1, prev2 + value), then shift: prev2 = prev1, prev1 = current. After the range, prev1 is the answer for it.

  1. If n == 1, return nums[0].
  2. Run the rolling-variable House Robber on 0 .. n-2 and on 1 .. n-1.
  3. Return the larger result.

Implementation

Python:

from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]  # a single house has no neighbor

        def rob_line(lo: int, hi: int) -> int:
            prev2, prev1 = 0, 0  # best totals two houses back and one house back
            for i in range(lo, hi + 1):
                prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
            return prev1

        n = len(nums)
        # Either the last house is skipped or the first house is skipped
        return max(rob_line(0, n - 2), rob_line(1, n - 1))

Java:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }

    private int robLine(int[] nums, int lo, int hi) {
        int prev2 = 0, prev1 = 0;  // best totals two houses back and one house back
        for (int i = lo; i <= hi; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

Go:

func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0] // a single house has no neighbor
    }
    // Either the last house is skipped or the first house is skipped
    return max(robLine(nums[:n-1]), robLine(nums[1:]))
}

// robLine solves House Robber on a straight street in O(1) extra space.
func robLine(houses []int) int {
    prev2, prev1 := 0, 0 // best totals two houses back and one house back
    for _, v := range houses {
        prev2, prev1 = prev1, max(prev1, prev2+v)
    }
    return prev1
}

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length;
    if (n === 1) return nums[0]; // a single house has no neighbor

    const robLine = (lo, hi) => {
        let prev2 = 0, prev1 = 0; // best totals two houses back and one house back
        for (let i = lo; i <= hi; i++) {
            const current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    };

    // Either the last house is skipped or the first house is skipped
    return Math.max(robLine(0, n - 2), robLine(1, n - 1));
};

C#:

using System;

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return Math.Max(RobLine(nums, 0, n - 2), RobLine(nums, 1, n - 1));
    }

    private int RobLine(int[] nums, int lo, int hi) {
        int prev2 = 0, prev1 = 0;  // best totals two houses back and one house back
        for (int i = lo; i <= hi; i++) {
            int current = Math.Max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

C++:

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];  // a single house has no neighbor
        // Either the last house is skipped or the first house is skipped
        return max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }

private:
    int robLine(const vector<int>& nums, int lo, int hi) {
        int prev2 = 0, prev1 = 0;  // best totals two houses back and one house back
        for (int i = lo; i <= hi; i++) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
};

Complexity Analysis

  • Time: O(n). Two linear passes.
  • Space: O(1). Only two running totals per pass (the Go slices nums[:n-1] and nums[1:] share the original array and copy nothing).

Key Insights

  • Break the cycle by excluding one endpoint. A circular constraint between the first and last element is handled by solving two linear versions, one without each endpoint.
  • The two cases cover every valid plan. A valid plan cannot use both endpoints, so it skips at least one of them and appears in at least one of the two ranges. Overlap between the cases (plans that skip both) is harmless when taking a maximum.
  • Reuse, do not rewrite. The linear House Robber routine is used unchanged as a helper.
  • No overflow risk. At most 100 houses of at most 1000 each gives a total of at most 100,000.

Edge Cases

  • One house: return nums[0]. Without this check the two ranges are empty, and the table versions would index past the end.
  • Two houses: they are adjacent both ways, so the answer is the larger one; the two ranges are single houses.
  • Three houses: every pair is adjacent, so the answer is the maximum single value (Example 1).
  • All zeros: the answer is 0.
  • Best linear answer uses both endpoints: Example 3, where the straight-street answer of 10 is not allowed.

Common Mistakes

  • Running linear House Robber on the whole array. It may pick both nums[0] and nums[n - 1], as in [5, 1, 1, 5].
  • Forgetting n == 1. Both ranges become empty, and you return 0 or crash instead of returning the single house.
  • Excluding both endpoints in one pass. Solving only 1 .. n-2 misses plans that rob house 0 or house n - 1.
  • Off-by-one in the ranges. The two ranges are 0 .. n-2 and 1 .. n-1, each of length n - 1.

Interview Tips

  • Solve or recall the linear version first, then explain exactly which constraint the circle adds.
  • State the two-case argument out loud: “a valid plan cannot use both endpoints, so it lives entirely in one of the two linear ranges.”
  • Write the linear solver as a helper that takes a range or a slice, so the main function is three lines.
  • Test with [5, 1, 1, 5] and a single house before declaring the code done.

Follow-up Questions

  • What if the houses form a binary tree instead of a line or circle? That is House Robber III: a tree DP returning (best with this node robbed, best with it skipped) for every node.
  • How would you return which houses to rob? Keep the DP table from Approach 1 for the winning range and walk backward from the end: if dp[i] != dp[i - 1], the i-th house of the range was robbed and you jump to i - 2; otherwise move to i - 1.
  • What if you had to skip at least two houses between robberies? Change the recurrence to dp[i] = max(dp[i - 1], dp[i - 3] + value). The circular split must change too, because house 0 now also conflicts with house n - 2. Take the better of two cases: skip house 0 and solve the line of houses 1 to n - 1, or rob house 0 and add the best line answer for houses 3 to n - 3.
  • Could you do it in a single pass? Yes, by running both rolling-variable states in the same loop, but it is still two DP computations and the code is harder to read.