House Robber II

medium
Dynamic ProgrammingArrayDynamic Programming

Given an integer array nums representing the amount of money at each house arranged in a circle, return the maximum amount you can rob tonight without robbing two adjacent houses. Since the houses form a circle, the first and last houses are also adjacent.

Examples

Example 1

  • Input: nums = [2,3,2]
  • Output: 3
  • Explanation: You cannot rob house 1 (money = 2) and house 3 (money = 2) because they are adjacent in the circle. Rob house 2 (money = 3).

Example 2

  • Input: nums = [1,2,3,1]
  • Output: 4
  • Explanation: Rob house 1 (money = 1) and house 3 (money = 3). Total = 1 + 3 = 4.

Example 3

  • Input: nums = [1,2,3]
  • Output: 3
  • Explanation: Rob house 3 (money = 3).

Constraints

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

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursion (Brute Force)

Intuition

The circular constraint means the first and last houses cannot both be robbed. We can break this into two linear subproblems: one that considers houses 0 through n-2 (excluding the last) and another that considers houses 1 through n-1 (excluding the first). For each subproblem, we use the same recursive approach as House Robber I: at each house, choose to rob or skip.

Algorithm

  1. If there is only one house, return its value.
  2. Solve the linear House Robber problem for `nums[0..n-2]`.
  3. Solve the linear House Robber problem for `nums[1..n-1]`.
  4. Return the maximum of the two results.
TimeO(2^n) for each subproblem without memoizationSpaceO(n) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int robLinear(vector<int>& nums, int start, int end) {
        if (start > end) return 0;
        return max(nums[start] + robLinear(nums, start + 2, end),
                   robLinear(nums, start + 1, end));
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }
};
Java 21
class Solution {
    private int robLinear(int[] nums, int start, int end) {
        if (start > end) return 0;
        return Math.max(nums[start] + robLinear(nums, start + 2, end),
                        robLinear(nums, start + 1, end));
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }
}
Python 3.12
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob_linear(start: int, end: int) -> int:
            if start > end:
                return 0
            return max(nums[start] + rob_linear(start + 2, end),
                       rob_linear(start + 1, end))

        n = len(nums)
        if n == 1:
            return nums[0]
        return max(rob_linear(0, n - 2), rob_linear(1, n - 1))
Go 1.26
func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    var robLinear func(start, end int) int
    robLinear = func(start, end int) int {
        if start > end {
            return 0
        }
        take := nums[start] + robLinear(start+2, end)
        skip := robLinear(start+1, end)
        if take > skip {
            return take
        }
        return skip
    }
    a := robLinear(0, n-2)
    b := robLinear(1, n-1)
    if a > b {
        return a
    }
    return b
}
Approach 2

Dynamic Programming (Bottom-Up)

Intuition

We reduce the circular problem to two linear problems: rob houses 0 to n-2 or houses 1 to n-1. For each linear subproblem, we use bottom-up DP where dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The answer is the maximum of both runs.

Algorithm

  1. If `n == 1`, return `nums[0]`.
  2. Write a helper that solves the linear House Robber for a given range using a DP array.
  3. Call the helper for range `[0, n-2]` and `[1, n-1]`.
  4. Return the maximum of the two results.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        if (start == end) return nums[start];
        int n = end - start + 1;
        vector<int> dp(n);
        dp[0] = nums[start];
        dp[1] = max(nums[start], nums[start + 1]);
        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }
        return dp[n - 1];
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
};
Java 21
class Solution {
    private int robRange(int[] nums, int start, int end) {
        if (start == end) return nums[start];
        int n = end - start + 1;
        int[] dp = new int[n];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[start + i]);
        }
        return dp[n - 1];
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
}
Python 3.12
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob_range(start: int, end: int) -> int:
            if start == end:
                return nums[start]
            n = end - start + 1
            dp = [0] * n
            dp[0] = nums[start]
            dp[1] = max(nums[start], nums[start + 1])
            for i in range(2, n):
                dp[i] = max(dp[i - 1], dp[i - 2] + nums[start + i])
            return dp[n - 1]

        n = len(nums)
        if n == 1:
            return nums[0]
        return max(rob_range(0, n - 2), rob_range(1, n - 1))
Go 1.26
func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    robRange := func(start, end int) int {
        if start == end {
            return nums[start]
        }
        length := end - start + 1
        dp := make([]int, length)
        dp[0] = nums[start]
        dp[1] = nums[start]
        if nums[start+1] > dp[1] {
            dp[1] = nums[start+1]
        }
        for i := 2; i < length; i++ {
            dp[i] = dp[i-1]
            if dp[i-2]+nums[start+i] > dp[i] {
                dp[i] = dp[i-2] + nums[start+i]
            }
        }
        return dp[length-1]
    }
    a := robRange(0, n-2)
    b := robRange(1, n-1)
    if a > b {
        return a
    }
    return b
}
Approach 3

Space-Optimized DP

Intuition

We apply the same two-range decomposition but use only two variables per linear subproblem instead of a full DP array. This reduces the space from O(n) to O(1) while maintaining O(n) time.

Algorithm

  1. If `n == 1`, return `nums[0]`.
  2. For each range, use two variables `prev2` and `prev1` to track the last two DP states.
  3. Iterate through the range, updating `current = max(prev1, prev2 + nums[i])`.
  4. Return the maximum result from both ranges.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int robRange(vector<int>& nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int curr = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
};
Java 21
class Solution {
    private int robRange(int[] nums, int start, int end) {
        int prev2 = 0, prev1 = 0;
        for (int i = start; i <= end; i++) {
            int curr = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
}
Python 3.12
from typing import List

class Solution:
    def rob(self, nums: List[int]) -> int:
        def rob_range(start: int, end: int) -> int:
            prev2, prev1 = 0, 0
            for i in range(start, end + 1):
                curr = max(prev1, prev2 + nums[i])
                prev2 = prev1
                prev1 = curr
            return prev1

        n = len(nums)
        if n == 1:
            return nums[0]
        return max(rob_range(0, n - 2), rob_range(1, n - 1))
Go 1.26
func rob(nums []int) int {
    n := len(nums)
    if n == 1 {
        return nums[0]
    }
    robRange := func(start, end int) int {
        prev2, prev1 := 0, 0
        for i := start; i <= end; i++ {
            curr := prev1
            if prev2+nums[i] > curr {
                curr = prev2 + nums[i]
            }
            prev2 = prev1
            prev1 = curr
        }
        return prev1
    }
    a := robRange(0, n-2)
    b := robRange(1, n-1)
    if a > b {
        return a
    }
    return b
}

Frequently asked questions

What is the optimal time complexity of House Robber II?

The most efficient approach in this guide ("Space-Optimized DP") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does House Robber II use?

House Robber II is a medium-level Dynamic Programming problem involving Array, Dynamic Programming. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can House Robber II be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[2,3,2]
Expected Output
3