What is the time complexity of House Robber?

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

What data structures are used to solve House Robber?

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?

Insight 1: The optimal solution for robbing up to house `i` depends on the optimal solutions for robbing up to house `i-1` and `i-2`. This suggests a dynamic programming approach. Insight 2: We don't need to store the optimal solutions for all houses. Only the last two optimal solutions are required to calculate the current one. This allows for space optimization.

Which companies ask LeetCode 198. House Robber in interviews?

This problem is frequently asked at Accenture, Agoda, Airbnb, Arcesium, ByteDance and 25 more companies.

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

House Robber - LeetCode 198 Solution

House Robber - Complete Solution Guide

House Robber is LeetCode problem 198, 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, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 money you can rob tonight without alerting the police .

Detailed Explanation

The problem presents a scenario where a professional robber plans to rob houses along a street. Each house contains a certain amount of money. However, adjacent houses have connected security systems, meaning that if two adjacent houses are robbed on the same night, the police will be alerted. The goal is to determine the maximum amount of money the robber can steal without triggering the alarm (i.e., without robbing adjacent houses). The input is an array of integers `nums`, where `nums[i]` represents the amount of money in the i-th house. The output should be the maximum possible amount of money that can be robbed.

Solution Approach

The solution utilizes dynamic programming with space optimization. It maintains two variables, `rob1` and `rob2`, to store the maximum amount of money that can be robbed up to the previous house and up to two houses ago, respectively. For each house, the algorithm checks if it's more profitable to rob the current house (which means we can't rob the previous one, so we add the current house's money to `rob2`) or not rob the current house (in which case we take the maximum we could rob up to the previous house, `rob1`). The algorithm then updates `rob2` to `rob1` and `rob1` to the maximum amount calculated for the current house.

Step-by-Step Algorithm

Step 1: Initialize two variables, `rob1` and `rob2`, to 0. `rob1` represents the maximum amount of money that can be robbed up to the previous house, and `rob2` represents the maximum amount that can be robbed up to two houses ago.
Step 2: Iterate through the `nums` array.
Step 3: For each house `n` in `nums`, calculate the maximum amount that can be robbed by either robbing the current house (n + rob2) or not robbing the current house (rob1). Store this value in a temporary variable `temp`.
Step 4: Update `rob2` to `rob1` and `rob1` to `temp`. This shifts the 'window' to consider the next house.
Step 5: After iterating through all the houses, `rob1` will contain the maximum amount of money that can be robbed without robbing adjacent houses. Return `rob1`.

Key Insights

Insight 1: The optimal solution for robbing up to house `i` depends on the optimal solutions for robbing up to house `i-1` and `i-2`. This suggests a dynamic programming approach.
Insight 2: We don't need to store the optimal solutions for all houses. Only the last two optimal solutions are required to calculate the current one. This allows for space optimization.
Insight 3: Consider the base cases: if there's only one house, rob it. If there are two houses, rob the house with more money.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Array, Dynamic Programming.

Companies

Asked at: Accenture, Agoda, Airbnb, Arcesium, ByteDance, CARS24, Cisco, Citadel, Cleartrip, DE Shaw, Databricks, Datadog, EPAM Systems, Expedia, Flipkart, Goldman Sachs, Infosys, Intuit, LinkedIn, Morgan Stanley, Nordstrom, Nvidia, PayPal, PhonePe, Salesforce, ServiceNow, Tesla, Turing, Walmart Labs, Zoho.

House Robber | LeetCode 198

Medium

Array Dynamic Programming

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

Solution Code

Available in:

class Solution {
    public int rob(int[] nums) {
        int rob1 = 0, rob2 = 0;

        // [rob2, rob1, n, n+1, ...]
        // rob1: max money robbing up to the previous house
        // rob2: max money robbing up to two houses ago
        for (int n : nums) {
            // At current house 'n', the max money is either:
            // 1. rob this house (n + rob2)
            // 2. don't rob this house (rob1)
            int temp = Math.max(n + rob2, rob1);
            rob2 = rob1;
            rob1 = temp;
        }
        
        return rob1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 198: House Robber - Detailed explanation and solution approaches.

Topics

Array Dynamic Programming

Companies

AccentureAgodaAirbnbArcesiumByteDanceCARS24CiscoCitadel

Stats

Difficulty:Medium

Languages:4

Companies:30

Problem #:198

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: Initialize two variables, `rob1` and `rob2`, to 0. `rob1` represents the maximum amount of money that can be robbed up to the previous house, and `rob2` represents the maximum amount that can be robbed up to two houses ago.
2
Step 2: Iterate through the `nums` array.
3
Step 3: For each house `n` in `nums`, calculate the maximum amount that can be robbed by either robbing the current house (n + rob2) or not robbing the current house (rob1). Store this value in a temporary variable `temp`.
4
Step 4: Update `rob2` to `rob1` and `rob1` to `temp`. This shifts the 'window' to consider the next house.
5
Step 5: After iterating through all the houses, `rob1` will contain the maximum amount of money that can be robbed without robbing adjacent houses. Return `rob1`.

💡

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 time complexity is linear because the algorithm processes each house exactly once. The space complexity is constant because the algorithm uses a fixed number of variables (2 in this case) to store intermediate results, irrespective of the input array's size.

📖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

Dynamic Programming with Array

Use an array `dp` of size `n` (or `n+1`) to store the maximum amount that can be robbed up to each house. `dp[i]` stores the maximum amount that can be robbed up to house `i`. The recurrence relation is `dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])`.

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

Trade-offs: This approach is easier to understand for beginners, but it uses more space than the optimized solution. Use this if space is not a primary concern and code readability is more important.

✨

Key Insights

1Insight 1: The optimal solution for robbing up to house `i` depends on the optimal solutions for robbing up to house `i-1` and `i-2`. This suggests a dynamic programming approach.
2Insight 2: We don't need to store the optimal solutions for all houses. Only the last two optimal solutions are required to calculate the current one. This allows for space optimization.
3Insight 3: Consider the base cases: if there's only one house, rob it. If there are two houses, rob the house with more money.

📚

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: Empty input array (`nums` is empty). The algorithm correctly returns 0 since the loop won't execute, and `rob1` remains 0.
Edge case 2: Single house in the input array (`nums` contains one element). The algorithm iterates once, and `rob1` becomes the value of that single house, which is then returned.
Edge case 3: Two houses in the input array (`nums` contains two elements). The algorithm will correctly calculate `max(nums[0], nums[1])` and return the greater value. Specifically in the first loop `temp` would be `max(nums[0] + 0, 0)` then in second loop `temp` would be `max(nums[1] + nums[0], nums[0])`

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting the base cases (empty or single-house array). Properly handling these cases is crucial for the algorithm to work correctly.

✗Common mistake 2: Incorrectly implementing the dynamic programming recurrence relation. It's important to understand that robbing the current house prevents robbing the previous one.

✗Common mistake 3: Not using the optimized O(1) space approach when it's possible. The problem constraints often allow for space optimization, which is preferable if possible.

✅

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: Resource allocation. Imagine you have a limited number of resources to allocate to different projects. Each project has a certain value, but some projects might be mutually exclusive (e.g., competing projects that require the same equipment). The House Robber problem helps determine the optimal allocation strategy.

🏦Real-world scenario 2: Scheduling non-overlapping tasks. If you have a list of tasks, each with a specific duration and a reward, and some tasks cannot be performed concurrently (they would overlap). Determining which set of tasks to perform to maximize the overall reward is an analogous problem to the House Robber.

💡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: June 19, 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 14

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

@TechLeadJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

How do I identify if a problem needs dynamic programming?

DP problems typically have: 1) Overlapping subproblems (same calculation repeated), 2) Optimal substructure (optimal solution uses optimal solutions to subproblems). Look for keywords like "minimum/maximum," "count ways," "is it possible," or "longest/shortest."

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "House Robber"?

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?