What is the time complexity of House Robber II?

The optimal solution has a time complexity of O(n).

What data structures are used to solve House Robber II?

This problem uses Array, Dynamic Programming. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving House Robber II?

Insight 1: Breaking the circle: The circular arrangement can be handled by considering two separate scenarios: one where you rob houses from index 0 to n-2 (excluding the last house) and another where you rob houses from index 1 to n-1 (excluding the first house). Insight 2: Dynamic Programming: The linear robbing problem (robbing houses in a straight line) can be efficiently solved using dynamic programming. The core idea is to keep track of two values: the maximum amount that can be robbed including the current house and the maximum amount that can be robbed excluding the current house.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

House Robber II - LeetCode 213 Solution

Q: Which companies ask LeetCode 213. House Robber II in interviews?

This problem is frequently asked at ByteDance, Databricks, Datadog, Docusign, LinkedIn and 4 more companies.

House Robber II - Complete Solution Guide

House Robber II is LeetCode problem 213, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 a security system 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

Detailed Explanation

The House Robber II problem extends the original House Robber problem by introducing a circular arrangement of houses. Given an array `nums` representing the amount of money in each house, the goal is to find the maximum amount of money you can rob without robbing adjacent houses. The key difference from House Robber I is that the first and last houses are now considered neighbors, creating a circular dependency. This means you cannot rob both the first and last houses simultaneously.

Solution Approach

The solution addresses the circular dependency by splitting the problem into two subproblems, each representing a linear arrangement of houses. In the first subproblem, the last house is excluded, and in the second subproblem, the first house is excluded. This ensures that the first and last houses are not robbed simultaneously. The maximum robbery amount is then calculated for each of these linear arrangements using dynamic programming. The algorithm iterates through each house in the given range. At each step, it updates the maximum amounts that can be robbed so far, ensuring no two adjacent houses are robbed.

Step-by-Step Algorithm

Step 1: Handle the base case: If the input array contains only one house, return the amount in that house.
Step 2: Define a helper function `_rob_linear(arr)` (or equivalent in other languages) to solve the House Robber problem for a linear array. This function uses dynamic programming with two variables, `rob1` and `rob2`, to store the maximum amount robbed up to the previous house and the current house, respectively.
Step 3: Calculate the maximum robbery amount for the subproblem excluding the last house: Call `_rob_linear(nums[:-1])` or the equivalent `_rob_linear(nums, 0, n-2)` in Java.
Step 4: Calculate the maximum robbery amount for the subproblem excluding the first house: Call `_rob_linear(nums[1:])` or the equivalent `_rob_linear(nums, 1, n-1)` in Java.
Step 5: Return the maximum of the two robbery amounts calculated in steps 3 and 4.

Key Insights

Insight 1: Breaking the circle: The circular arrangement can be handled by considering two separate scenarios: one where you rob houses from index 0 to n-2 (excluding the last house) and another where you rob houses from index 1 to n-1 (excluding the first house).
Insight 2: Dynamic Programming: The linear robbing problem (robbing houses in a straight line) can be efficiently solved using dynamic programming. The core idea is to keep track of two values: the maximum amount that can be robbed including the current house and the maximum amount that can be robbed excluding the current house.
Insight 3: Constant Space: The dynamic programming approach can be optimized to use constant space by storing only the previous two maximum values.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: ByteDance, Databricks, Datadog, Docusign, LinkedIn, Nordstrom, PhonePe, Visa, thoughtspot.

House Robber II | LeetCode 213

Medium

Array Dynamic Programming

Time: O(n)Space: O(1)

Solution Code

Available in:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }

        return Math.max(_rob_linear(nums, 0, n - 2), _rob_linear(nums, 1, n - 1));
    }

    private int _rob_linear(int[] arr, int start, int end) {
        int rob1 = 0;
        int rob2 = 0;
        for (int i = start; i <= end; i++) {
            int n = arr[i];
            int temp = Math.max(n + rob1, rob2);
            rob1 = rob2;
            rob2 = temp;
        }
        return rob2;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 213: House Robber II - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

ByteDanceDatabricksDatadogDocusignLinkedInNordstromPhonePeVisa

Stats

Difficulty:Medium

Languages:4

Companies:9

Problem #:213

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Handle the base case: If the input array contains only one house, return the amount in that house.
2
Step 2: Define a helper function `_rob_linear(arr)` (or equivalent in other languages) to solve the House Robber problem for a linear array. This function uses dynamic programming with two variables, `rob1` and `rob2`, to store the maximum amount robbed up to the previous house and the current house, respectively.
3
Step 3: Calculate the maximum robbery amount for the subproblem excluding the last house: Call `_rob_linear(nums[:-1])` or the equivalent `_rob_linear(nums, 0, n-2)` in Java.
4
Step 4: Calculate the maximum robbery amount for the subproblem excluding the first house: Call `_rob_linear(nums[1:])` or the equivalent `_rob_linear(nums, 1, n-1)` in Java.
5
Step 5: Return the maximum of the two robbery amounts calculated in steps 3 and 4.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The algorithm iterates through the array at most twice. The dominant operation is the `max` function within the loop of `_rob_linear`, which takes constant time. The space complexity is constant because only a few variables are used to store the previous maximum amounts.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a DP array

Instead of using constant space, we can use a DP array of size `n` to store the maximum robbery amount at each house. The recurrence relation would be `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`.

Time: O(n)Space: O(n)

Trade-offs: This approach is easier to understand but requires O(n) space. It can be beneficial for debugging or when space complexity is not a major concern.

✨

Key Insights

1Insight 1: Breaking the circle: The circular arrangement can be handled by considering two separate scenarios: one where you rob houses from index 0 to n-2 (excluding the last house) and another where you rob houses from index 1 to n-1 (excluding the first house).
2Insight 2: Dynamic Programming: The linear robbing problem (robbing houses in a straight line) can be efficiently solved using dynamic programming. The core idea is to keep track of two values: the maximum amount that can be robbed including the current house and the maximum amount that can be robbed excluding the current house.
3Insight 3: Constant Space: The dynamic programming approach can be optimized to use constant space by storing only the previous two maximum values.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Dynamic Programming

Breaking complex problems into smaller subproblems and storing results.

Edge Cases

Edge case 1: `nums` contains only one house. The solution handles this case by returning the value of that single house.
Edge case 2: `nums` contains two houses. The standard logic still correctly identifies the maximum of the two houses. No special case is required.
Edge case 3: Empty array: While not explicitly in constraints, an empty array could be a hypothetical edge case. The code does not explicitly handle this; however, depending on the implementation of the slice, the behavior might vary. In Python, the slice `nums[:-1]` will return an empty array when nums is empty, resulting in `_rob_linear` returning 0. Similarly `nums[1:]` handles it. In other languages the behavior might not be well defined. Consider handling this edge case by returning 0 if the array is empty.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to split the problem into two subproblems (excluding the first house or excluding the last house). This leads to incorrect results because it might violate the circular constraint.

✗Common mistake 2: Incorrectly implementing the dynamic programming step in `_rob_linear`. It is crucial to correctly update `rob1` and `rob2` to keep track of the maximum amounts.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing resource allocation in a network where adjacent resources cannot be used simultaneously due to interference or dependencies.

🏦Real-world scenario 2: Scheduling tasks in a pipeline where adjacent tasks cannot be executed concurrently due to resource constraints or conflicts. Maximizing the profit from projects, where some projects cannot be simultaneously selected due to budget or personnel limitations.

🎮Real-world scenario 3: Choosing investment opportunities where some investments are mutually exclusive (e.g., investing in two competing companies). The goal is to maximize the total return while avoiding conflicting investments.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 4, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Should I use top-down (memoization) or bottom-up (tabulation)?

Start with top-down (recursion + memoization) as it directly maps to the recursive thinking and handles only needed subproblems. Convert to bottom-up for better space efficiency and to avoid stack overflow. Bottom-up is often faster due to no recursion overhead.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "House Robber II"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether dynamic programming techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?