House Robber II
House Robber II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 1D Array (Fibonacci Style) subpattern.
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 money you can rob tonight without alerting the police.
Example 1:
Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 3:
Input: nums = [1,2,3] Output: 3
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Topics and companies
Topics: Array, Dynamic Programming.
Reported in interviews at eBay, Google, Microsoft.
How to practise House Robber II on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.
Open House Robber II in the code editor, or read the House Robber II editorial for a worked solution with its approach and complexity analysis.
Where House Robber II sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 1D Array (Fibonacci Style) subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to House Robber II
Other problems that use the same 1D Array (Fibonacci Style) and Dynamic Programming (DP) Patterns techniques:
- Climbing Stairs — Easy, same subpattern
- Decode Ways — Medium, same subpattern
- Delete and Earn — Medium, same subpattern
- Fibonacci Number — Easy, same subpattern
- House Robber — Medium, same subpattern
- Min Cost Climbing Stairs — Easy, same subpattern