House Robber II

MediumDynamic ProgrammingArray
Category: 1-D Dynamic Programming
Companies that ask this question:
AmazonMicrosoftGoogleFacebook

Approach

House Robber II

Problem 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 security systems 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.

Approach

This problem is a variation of House Robber I with an additional constraint: houses are arranged in a circle.

Key Insights

  1. Circular Constraint: If we rob the first house, we cannot rob the last house, and vice versa
  2. Solution Strategy: Run House Robber I algorithm twice:
    • Scenario 1: Rob houses [0..n-2] (exclude the last house)
    • Scenario 2: Rob houses [1..n-1] (exclude the first house)
    • Return the maximum of both scenarios
  3. House Robber I Algorithm: Use two variables:
    • rob: Maximum money if we rob the current house
    • notRob: Maximum money if we skip the current house
    • Update: newRob = notRob + nums[i], newNotRob = max(rob, notRob)

Algorithm

  1. Handle edge cases (1 or 2 houses)
  2. Run linear House Robber on [0..n-2]
  3. Run linear House Robber on [1..n-1]
  4. Return the maximum of both results

Complexity Analysis

  • Time Complexity: O(n) - two linear passes
  • Space Complexity: O(1) - only using two variables for tracking state

Solution

java
1class Solution {
2    public int rob(int[] nums) {
3        int n = nums.length;
4        if (n == 1) return nums[0];
5        if (n == 2) return Math.max(nums[0], nums[1]);
6
7        // Since houses are in a circle, we cannot rob both first and last house
8        // Solution: Run House Robber I twice
9        // 1. Exclude last house (rob houses 0 to n-2)
10        // 2. Exclude first house (rob houses 1 to n-1)
11        // Return the maximum of both scenarios
12
13        int scenario1 = robLinear(nums, 0, n - 2);
14        int scenario2 = robLinear(nums, 1, n - 1);
15
16        return Math.max(scenario1, scenario2);
17    }
18
19    private int robLinear(int[] nums, int start, int end) {
20        int rob = 0, notRob = 0;
21
22        for (int i = start; i <= end; i++) {
23            int newRob = notRob + nums[i];
24            int newNotRob = Math.max(rob, notRob);
25            rob = newRob;
26            notRob = newNotRob;
27        }
28
29        return Math.max(rob, notRob);
30    }
31}
32
Loading visualizer...