House Robber II

NeetCode: House Robber II · LeetCode: 213. House Robber II · Difficulty: Medium

This is House Robber with the houses arranged in a circle: the first and last houses are neighbours too. Return the maximum you can rob without touching two adjacent houses.

Example

Text

Input:  nums = [2, 3, 2]       Output: 3    (houses 0 and 2 are adjacent, so only one of the 2s)
Input:  nums = [1, 2, 3, 1]    Output: 4

Brute force: enumerate every subset

Represent a choice of houses as a bitmask. A mask is valid if no two chosen houses are adjacent, including the pair (last, first). The answer is the best valid sum. This is feasible only for small n: the mask is an int, so n must be at most 30, and the loop already runs 2^n times.

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        int best = 0;
        for (int mask = 0; mask < (1 << n); mask++) {
            boolean adjacent = (mask & (mask >> 1)) != 0;
            boolean wraps = (mask & 1) != 0 && (mask & (1 << (n - 1))) != 0;
            if (adjacent || wraps) {
                continue;
            }
            int sum = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    sum += nums[i];
                }
            }
            best = Math.max(best, sum);
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{2, 3, 2}));
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{1, 2, 3}));
        System.out.println(solution.rob(new int[]{5}));
    }
}

Output

Time: O(2^n · n). Space: O(1).

Optimal: two linear House Robber runs

In any valid answer the first and last houses are not both robbed. So the answer is the better of two independent linear problems: houses 0..n-1 (last one excluded) and houses 1..n (first one excluded). Each is exactly House Robber, solved in one pass with two variables (robLine). A single house is a special case, because both ranges would be empty.

Java

class Solution {
    // Best loot from houses lo..hi (inclusive), as in House Robber.
    private int robLine(int[] nums, int lo, int hi) {
        int prev2 = 0;
        int prev1 = 0;
        for (int i = lo; i <= hi; i++) {
            int cur = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return nums[0];
        }
        return Math.max(robLine(nums, 0, n - 2), robLine(nums, 1, n - 1));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{2, 3, 2}));
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{1, 2, 3}));
        System.out.println(solution.rob(new int[]{5}));
    }
}

Output

Time: O(n). Space: O(1). Java arrays have no slices, so robLine takes the index range lo..hi instead of copying the subarray with Arrays.copyOfRange, which would cost O(n) extra space.