213. House Robber II

Time: O(n)

Space: O(1)

Intuition

The circular constraint means houses 0 and n-1 cannot both be robbed. Break the circle by solving two independent sub-problems: one excluding the first house, one excluding the last. The answer is the maximum of both. Each sub-problem is the classic linear House Robber.

Algorithm

1If n == 1, return nums[0].
2Define Rob(start, end): run the rolling-variable DP on nums[start..end]. O(n) time, O(1) space.
3Return max(Rob(0, n-2), Rob(1, n-1)).

Example Walkthrough

Input: nums = [2,3,2]

1.Sub-problem 1 (exclude last): Rob([2,3]). Best = 3.
2.Sub-problem 2 (exclude first): Rob([3,2]). Best = 3.
3.Return max(3,3) = 3.

Output: 3

Common Pitfalls

•Do not try to "stitch" the two sub-problems together - they are fully independent.
•Edge case n=1: return nums[0] before calling Rob, since Rob(0, -1) would have an empty range.

213.cs

// Approach: The circular layout means the first and last houses cannot both be robbed.
// Break the circle into two overlapping linear sub-problems: houses [0..n-2] and houses [1..n-1].
// Apply the standard House Robber DP on each range: dp = max(skip current, take current + dp[i-2]).
// Use two rolling variables so each linear pass runs in O(1) space.
// The answer is the maximum result from the two sub-problems.
// Time: O(n) Space: O(1) using rolling variables.

public class Solution
{
    public int Rob(int[] nums)
    {
        int n = nums.Length;
        List<int> arr1 = new List<int>();
        List<int> arr2 = new List<int>();

        if (n == 1)
            return nums[0];

        for (int i = 0; i < n; i++)
        {
            if (i != 0)
                arr1.Add(nums[i]);
            if (i != n - 1)
                arr2.Add(nums[i]);
        }

        int ans1 = topDown(arr1);
        int ans2 = topDown(arr2);

        return Math.Max(ans1, ans2);
    }

    private int topDown(List<int> arr)
    {
        int n = arr.Count;
        int prev = arr[0];
        int prev2 = 0;

        for (int i = 1; i < n; i++)
        {
            int pick = arr[i];
            if (i > 1)
                pick += prev2;
            int nonPick = 0 + prev;

            int cur_i = Math.Max(pick, nonPick);
            prev2 = prev;
            prev = cur_i;
        }
        return prev;
    }
}

Was this solution helpful?