213. House Robber II


Problem Description

In this problem, we imagine a situation where a professional thief is planning to rob houses. The houses are laid out in a circle, and each house contains a certain amount of money that can be stolen. However, if the robber tries to rob two adjacent houses, an alarm will be triggered and the police will be notified. The objective is to determine the maximum amount of money that can be stolen without triggering any alarms.

Constraints include:

  • The arrangement of the houses in a circle, which means that the first and last houses are considered adjacent.
  • One cannot rob two adjacent houses on the same night.

Given the circular arrangement, we need to find a way to calculate the maximum loot without robbing adjacent houses and also accounting for the circular layout.

Intuition

The problem can be seen as a variation of the classic dynamic programming problem "House Robber", with the additional constraint imposed by the circular arrangement of the houses.

The intuition for solving this problem is to use dynamic programming to make decisions at each step. We need to figure out, with each house, whether it's more profitable to rob it or skip it. However, the circular arrangement makes it tricky; we cannot simply start from one end and go to the other, as we may miss out on the optimal solution that involves wrapping around the end.

To resolve this issue with circular arrangement, we make use of the following observations:

  • If we rob the first house, we cannot rob the last house due to the circular layout.
  • If we ignore the first house, we can treat the problem as a non-circular arrangement and apply standard dynamic programming as in the original "House Robber" problem.

So our approach is:

  1. Calculate the maximum money that can be robbed bypassing the first house (making the problem linear instead of circular).
  2. Calculate the maximum money that can be robbed if we skip the last house for the same reason.

After calculating these two scenarios, the maximum of both will give us the solution to the original circular problem. The function _rob implements this approach of robbing or skipping a house. It iterates through the given list of house values and, at each step, decides whether to rob the current house or not. The choice is made based on the maximum money that can be gained considering the previous decisions.

The rob function then calls the helper function _rob twice – once for the array of houses excluding the first house and once for the array excluding the last house – and returns the maximum of the two results. This accommodates the circular constraint by considering both possibilities – starting from the first house or skipping it.

In summary, the solution splits the circular problem into two linear sub-problems and applies dynamic programming to each. The maximum of the solutions to these sub-problems is the answer to the original problem.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the relationship between a tree and a graph?

Solution Approach

The solution provided uses dynamic programming, a method for solving complex problems by breaking them down into simpler sub-problems. It is particularly well-suited for optimization problems like ours, where we seek the maximum amount of money that can be robbed.

Dynamic programming often involves creating an array to store the sub-problems' solutions; however, in this implementation, only two variables are maintained, reducing the space complexity. The algorithm employs a "rob-or-skip" strategy, where we look at each house and decide whether to rob it or skip it based on which action would yield a higher profit. Here's how the variables f and g correspond to this strategy:

  • f: The maximum amount of money that can be robbed up to the current house without robbing it (essentially, the skip option).
  • g: The maximum amount of money that can be robbed including the current house (which is the sum of the money in the current house and the maximum amount robbed up to the previous house where we did not rob, to ensure no two adjacent houses are robbed).

The main function rob distinguishes between two cases due to the circular layout of houses. If there's only one house, it simply returns its value, as there's no constraint to consider. In other cases, the function utilizes a helper function _rob. The _rob function implements the dynamic programming approach and is applied to two slices of the original list: one excluding the first house and one excluding the last house.

Let's understand how _rob works:

  1. Initialize f, g to 0. These are the maximum amounts with the aforementioned conditions.
  2. Loop through each value x in the nums list, where x represents the amount of money in the current house:
    • Calculate the new value of f as the maximum between the old f and g. This choice represents skipping the current house, so we take the best previous outcome.
    • Update g to be the sum of the old f (which represents the total money robbed up to the previous house without robbing it) and x (the amount in the current house). This represents robbing the current house.
  3. After the loop, the function returns the maximum amount between f and g which represents the maximum money the robber can achieve by either robbing or not robbing the last house in the list.

Back in the rob function, we then return the maximum value obtained from calling _rob with either of the list slices, thus concluding the approach and ensuring we consider the circular property of the problem.

The time complexity of the solution is O(n), where n is the number of houses, because it processes each house exactly once. The space complexity is O(1), because it uses a constant amount of extra space, despite the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a circular arrangement of houses with the following amounts of money: [2, 3, 2].

The thief has the following options:

  1. Rob the first house (with 2), and then can only rob the third house (with 2), totaling 4.
  2. Skip the first house, rob the second house (with 3), and then they have to skip the third house because they can’t rob adjacent houses.

Applying the two scenarios from our solution approach:

  1. If we ignore the first house, we treat the remaining houses [3, 2] as a linear problem. Using our dynamic programming approach:

    • Start with f and g both at 0.
    • For the first house (with 3), we update g to 0 + 3 (since f is still 0). Now f is 0 and g is 3.
    • For the second house (with 2), we update f to the maximum of previous f and g, which is 3. We then set g to the previous f value plus the current house's value, which is 0 + 2. Now f is 3 and g is 2.
    • The maximum of f and g is 3, which is the most we can rob from houses [3, 2].
  2. If we ignore the last house, we treat the remaining houses [2, 3] as a linear problem. Again, we apply dynamic programming:

    • Start with f and g both at 0.
    • For the first house (with 2), we update g to 0 + 2. Now f is 0 and g is 2.
    • For the second house (with 3), we update f to the maximum of previous f and g, which is 2. We then set g to the previous f value plus the current house's value, which is 0 + 3. Now f is 2 and g is 3.
    • The maximum of f and g is 3, the most we can rob from houses [2, 3].

After comparing the two scenarios, we see the maximum money the thief can rob without triggering any alarms is 3. Thus, the robber robs the second house with 3 in both cases, and the solution to the problem is 3. This demonstrates how the circular constraint is handled by considering the problem in a linear fashion for two slices of the array.

Not Sure What to Study? Take the 2-min Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Python Solution

1class Solution:
2    def rob(self, nums: List[int]) -> int:
3        def _rob_subsequence(sub_nums):
4            """
5            Calculate the maximum amount of money that can be
6            robbed from a subsequence of houses (sub_nums).
7            """
8            prev_max = curr_max = 0
9            for value in sub_nums:
10                # Update the prev_max and curr_max to include
11                # the current house in the robbery plan or not.
12                prev_max, curr_max = curr_max, max(curr_max, prev_max + value)
13            # The current maximum will be the solution for this subsequence.
14            return curr_max
15      
16        # If there's only one house, return its value.
17        if len(nums) == 1:
18            return nums[0]
19      
20        # Rob the houses by considering two scenarios:
21        # 1. Excluding the first house.
22        # 2. Excluding the last house.
23        # Take the maximum from these two options.
24        return max(_rob_subsequence(nums[1:]), _rob_subsequence(nums[:-1]))
25

Java Solution

1class Solution {
2    // The main function to compute the maximum amount of money that can be robbed.
3    public int rob(int[] nums) {
4        int houseCount = nums.length;
5
6        // If there's only one house, the maximum money is what's in that house.
7        if (houseCount == 1) {
8            return nums[0];
9        }
10
11        // Otherwise, find the maximum of two scenarios: excluding the first house or excluding the last house.
12        return Math.max(robMaxMoney(nums, 0, houseCount - 2), robMaxMoney(nums, 1, houseCount - 1));
13    }
14
15    // Helper function to calculate the max money that can be robbed in a specific range of houses.
16    private int robMaxMoney(int[] nums, int left, int right) {
17        // Initialize two variables to keep track of the two previous maximum values.
18        int inclPrev = 0; // This will hold the maximum amount including the previous house.
19        int exclPrev = 0; // This will hold the maximum amount excluding the previous house.
20
21        // Iterate through the range of houses.
22        for (int i = left; i <= right; ++i) {
23            // Calculate the new maximum including the current house.
24            int inclCurr = exclPrev + nums[i];
25          
26            // Calculate the new maximum excluding the current house by taking the maximum between inclPrev and exclPrev.
27            exclPrev = Math.max(inclPrev, exclPrev);
28          
29            // Update inclPrev to be used in the next iteration.
30            inclPrev = inclCurr;
31        }
32
33        // Return the maximum money that can be robbed within the specified range.
34        // Must consider the final value of inclPrev and exclPrev, since one of them will have the maximum.
35        return Math.max(inclPrev, exclPrev);
36    }
37}
38

C++ Solution

1class Solution {
2public:
3    // Main function to calculate the maximum amount of money that can be robbed.
4    int rob(vector<int>& nums) {
5        int n = nums.size();
6        // If there's only one house, return its value.
7        if (n == 1) {
8            return nums[0];
9        }
10        // Compare and return the maximum amount between robbing the first house or the second one.
11        return max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
12    }
13
14    // Helper function to calculate max amount from a range of houses.
15    int robRange(vector<int>& nums, int left, int right) {
16        int inclusive = 0; // This will store the max amount including the current house.
17        int exclusive = 0; // This will store the max amount excluding the current house.
18
19        // Iterate from the left to the right indices of the house range.
20        for (; left <= right; ++left) {
21            // Compute the new exclusive amount, which is the max of the previous inclusive and exclusive amounts.
22            int newExclusive = max(inclusive, exclusive);
23            // Update inclusive to be the sum of the old exclusive and current house value.
24            inclusive = exclusive + nums[left];
25            // Update exclusive to the newly computed value.
26            exclusive = newExclusive;
27        }
28        // Return the maximum of inclusive and exclusive amounts as the result.
29        return max(inclusive, exclusive);
30    }
31};
32

Typescript Solution

1function rob(nums: number[]): number {
2    // Determine the length of the array.
3    const numLength = nums.length;
4  
5    // Edge case: If there's only one house, return its value.
6    if (numLength === 1) {
7        return nums[0];
8    }
9  
10    // Helper function to rob a range of houses from index l to r, inclusive.
11    const robRange = (start: number, end: number): number => {
12        let robPrevious = 0; // Initialize to store the maximum amount that can be robbed up to the previous house
13        let robCurrent = 0;  // Initialize to store the maximum amount that can be robbed up to the current house
14
15        // Iterate from the start index to the end index, inclusive.
16        for (; start <= end; ++start) {
17            let robNext = Math.max(robPrevious, robCurrent); // The next 'previous' is the max of current and previous robbed amounts.
18            robCurrent = robPrevious + nums[start];          // Update the current to the sum of previous robbed amount and current house value.
19            robPrevious = robNext;                           // Move the 'next' value to 'previous' for the next iteration.
20        }
21      
22        // Return the maximum amount robbed between the last two houses.
23        return Math.max(robPrevious, robCurrent);
24    };
25  
26    // The maximum amount robbed will be the maximum of either robbing from the first house to the second-to-last house,
27    // or from the second house to the last one since we cannot rob adjacent houses.
28    return Math.max(robRange(0, numLength - 2), robRange(1, numLength - 1));
29}
30
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Time and Space Complexity

The given Python code defines a method rob that solves the house robber problem for a neighborhood arranged in a circle, meaning the first and last houses cannot be robbed together.

Time Complexity

The time complexity of the helper function _rob is O(n), where n is the number of elements in nums. It iterates through the list once and performs a constant time operation of max(f, g) and an addition operation f + x for each element.

The rob function calls the _rob function twice: once with nums[1:] and once with nums[:-1]. Since slicing a list is O(n) and the _rob function is also O(n), the total time complexity for each call is O(2n). Because the two calls do not depend on each other, the overall time complexity of rob remains O(n).

Final time complexity: O(n)

Space Complexity

The helper function _rob uses O(1) extra space, as it only keeps track of the two variables f and g.

However, the main function rob creates two slices of the nums input list: nums[1:] and nums[:-1]. Each of these slices is of size n-1, where n is the length of the original nums. The space taken up by these lists is significant.

Final space complexity: O(n), accounting for the space used by the list slices.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫