How do you solve House Robber on LeetCode?

House Robber (LeetCode #198) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The problem can be solved using dynamic programming by breaking it down into subproblems.

What is the brute force solution for House Robber?

The brute force approach for House Robber is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves exploring all possible combinations of houses to rob. This means checking every possible subset of houses to find the maximum amount of money that can be robbed without alerting the police. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve House Robber?

House Robber uses the following concepts: Array, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Array.

What are the interview tips for House Robber?

Explain your thought process clearly when discussing your approach. Be prepared to discuss time and space complexity. Practice writing code on a whiteboard or in a coding environment without syntax highlighting.

What are common mistakes when solving House Robber?

Not considering edge cases like empty arrays or arrays with only one house. Failing to properly initialize the dp array.

#198

House Robber

Medium

ArrayDynamic ProgrammingDynamic ProgrammingArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses dynamic programming to build up the maximum amount of money that can be robbed up to each house. By keeping track of the maximum amount robbed up to the previous house and the house before that, we can decide whether to rob the current house or skip it.

⚙️

Algorithm

4 steps

1Step 1: Create an array dp where dp[i] represents the maximum amount of money that can be robbed from the first i houses.
2Step 2: Initialize dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
3Step 3: Iterate through the houses from the 2nd index to the last, updating dp[i] as max(dp[i-1], dp[i-2] + nums[i]).
4Step 4: Return dp[n-1] as the result.

solution.py12 lines

1def rob(nums):
2    if not nums:
3        return 0
4    n = len(nums)
5    if n == 1:
6        return nums[0]
7    dp = [0] * n
8    dp[0] = nums[0]
9    dp[1] = max(nums[0], nums[1])
10    for i in range(2, n):
11        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
12    return dp[-1]

ℹ

Complexity note: The time complexity is O(n) because we only traverse the list of houses once. The space complexity is O(n) due to the dp array used to store the maximum amounts.

1The problem can be solved using dynamic programming by breaking it down into subproblems.
2Understanding the relationship between the current house and the previous two houses is crucial.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.