Start learning free

LESSON 448 OF 539 · DYNAMIC PROGRAMMING

House Robber II in C#: Two Linear Runs for a Circular Street

Practice O(n) Read the full explanation

You are a robber planning to rob houses that stand in a circle: house 0 comes after the last house, so the first house and the last house are neighbors. Each house has some money stashed, given in an array nums: house i holds nums[i].

Neighboring houses share a security system: if two adjacent houses are robbed on the same night, the police are alerted. Return the maximum amount of money you can rob tonight without alerting the police.

This is House Robber with one change: the street is now a circle, so the first and the last house can't both be robbed.

Example 1:

Input: nums = [2, 3, 2]
Output: 3
Explanation: House 0 and house 2 both hold 2, but they are neighbors in the circle, so they can't both be robbed. Rob house 1 (money 3).

Example 2:

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

Example 3:

Input: nums = [400, 0, 0, 400, 0, 0, 400]
Output: 800
Explanation: On a street with two ends, houses 0, 3 and 6 would give 1200. In the circle, house 6 is next to house 0, so only two of those three houses can be robbed, for example houses 0 and 3: 400 + 400 = 800.

Constraints:

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

Note:

Your algorithm should run in O(n) time, where n is the number of houses.

STEP 1 OF 12
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    House Robber Ii in C#, explained

    Problem overview

    Rob receives an int[] nums where nums[i] is the money in house i, and returns the most you can rob without robbing two neighbouring houses. The houses stand in a circle, so the last house is also next to house 0, and the first and last houses can't both be robbed.

    For [2,3,2] the answer is 3: houses 0 and 2 hold 2 each but are neighbours in the circle, so you rob house 1. For [1,2,3,1] the answer is 4, from houses 0 and 2 (1 + 3). For [400,0,0,400,0,0,400] the answer is 800. On a street with two ends, houses 0, 3 and 6 would give 1200, but in the circle house 6 touches house 0, so only two of those three can be taken.

    Approach: break the circle in two places

    On a straight street, the problem is the classic House Robber: walk along the houses keeping two running totals. The circle adds one rule, so reduce it to the straight case.

    Any valid plan leaves out the first house or the last house (or both), because they can't both be robbed. So:

    • the best plan that never uses the last house is the best on the straight street of houses 0 to n - 2;
    • the best plan that never uses the first house is the best on the straight street of houses 1 to n - 1.

    The answer is the larger of the two. A plan that uses neither end is counted in both, which is harmless, since we only want the maximum. Each run takes O(n) time, so the whole algorithm does too.

    Step by step

    1. Store the length: int n = nums.Length.
    2. One house: if n == 1, return nums[0]. A single house has no neighbour, so you rob it. The two runs below each leave out one house, and with one house that would leave nothing.
    3. Leave out the last house: withoutLast = RobRange(nums, 0, n - 2). The helper RobRange solves the straight street from start to end; the lesson assumes it exists and writes it afterwards.
    4. Leave out the first house: withoutFirst = RobRange(nums, 1, n - 1).
    5. Return Math.Max(withoutLast, withoutFirst).
    6. Write RobRange(int[] nums, int start, int end), a public method returning int.
    7. prev starts at 0: the best total up to two houses before the current one. Before the range begins, nothing has been robbed.
    8. curr starts at 0: the best total up to the house just before the current one.
    9. Loop i from start while i <= end. It is <= because house end belongs to the range.
    10. Decide house i: best = Math.Max(curr, prev + nums[i]). Either skip the house and keep curr, or rob it, which means house i - 1 stays untouched, so its money is added to prev.
    11. Slide the totals: prev = curr first, then curr = best. The order matters, because changing curr first would overwrite the value prev needs.
    12. Return curr, the best total for houses start to end.

    The solution in C#

    class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if (n == 1) {
            return nums[0];
        }
        int withoutLast = RobRange(nums, 0, n - 2);
        int withoutFirst = RobRange(nums, 1, n - 1);
        return Math.Max(withoutLast, withoutFirst);
    }

    public int RobRange(int[] nums, int start, int end) {
        int prev = 0;
        int curr = 0;
        for (int i = start; i <= end; i++) {
            int best = Math.Max(curr, prev + nums[i]);
            prev = curr;
            curr = best;
        }
        return curr;
    }
}

    C# details worth knowing:

    • The array is not copied. RobRange receives the same nums and two indexes. Slicing a copy of the array for each run would also work but costs extra memory for nothing.
    • Math.Max comes from System and takes two numbers of the same type; here both are int. C# method names are PascalCase, and so are Rob and RobRange.
    • Overflow is not a concern here. The lesson allows up to 100 houses of at most 1000 each, so a total is at most 100,000, far below the int limit of 2,147,483,647. In general, int arithmetic wraps silently when it overflows, without an exception.
    • The loop can be empty. With two houses, RobRange(nums, 0, 0) and RobRange(nums, 1, 1) each visit one house. With n == 1 the ranges would be 0 to -1 and 1 to 0, which the loop would skip and give 0; that is why the single-house case is handled first.

    Complexity

    Time: O(n). RobRange visits at most n - 1 houses, and Rob calls it twice, so each house is visited at most twice.

    Space: O(1). Only a handful of int variables are used, whatever the number of houses.

    Edge cases and common mistakes

    • One house. [5] returns 5. Without the n == 1 check, both ranges would be empty and the answer would be 0.
    • Two houses. [1,2] returns 2: they are neighbours, so only the richer one is robbed.
    • Running the straight solution on the whole array. For [2,3,2] it would rob houses 0 and 2 for 4, which the circle forbids. The correct answer is 3.
    • Off-by-one in the ranges. The first run ends at n - 2 and the second starts at 1; both ranges include their last house, which is why the loop uses <=.
    • Updating prev and curr in the wrong order. Setting curr = best before prev = curr makes both variables equal and loses the older total.

    Testing

    Running Rob on a few arrays gives:

    numsResult
    [2,3,2]3
    [1,2,3,1]4
    [400,0,0,400,0,0,400]800
    [5]5
    [1,2]2
    [2,7,9,3,1]11

    For [2,3,2], RobRange(nums, 0, 1) returns 3 and RobRange(nums, 1, 2) returns 3, so Rob returns 3.

    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free