### 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 security system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

Input:[2,3,2]Output:3Explanation:You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

**Example 2:**

Problem linkInput:[1,2,3,1]Output:4Explanation:Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

This is very similar to House Robber I problem where the only difference is the houses now form a circle (French fancy way calls it cul-de-sac). It's same DP algorithm except now we need to consider two cases: whether we rob the first house or not. If we rob the first house, we should not rob the last house. If we do not rob the first house, we can rob the last house. We can even reuse the rob() function in House Robber I problem

### Solutions

#### Use DP

Space Complexity: O(N) since we use extra arrays

## No comments:

## Post a Comment

Thank your for your comment! Check out us at https://baozitraining.org/ if you need mock interviews!