Practice/Amazon/Leetcode 213. House Robber II

Leetcode 213. House Robber II

CodingMust

Problem

You are planning to rob houses along a street where each house contains a certain amount of money. The houses are arranged in a circular pattern, meaning the first house is adjacent to the last house.

There is a security system in place: you cannot rob two adjacent houses without triggering an alarm. Given an array of non-negative integers representing the amount of money in each house, determine the maximum amount you can rob tonight without alerting the police.

Requirements

1. Return the maximum sum of money that can be robbed
2. You cannot rob two houses that are adjacent to each other
3. The first and last houses are considered adjacent (circular arrangement)
4. Handle edge cases like arrays with one or two houses

Constraints

• 1 ≤ houses.length ≤ 1000
• 0 ≤ houses[i] ≤ 10000
• Time complexity should be O(n)
• Space complexity should be O(1) or O(n)

Examples

Example 1:

Input: houses = [2, 3, 2] Output: 3 Explanation: You cannot rob house at index 0 (value = 2) and house at index 2 (value = 2) because they are adjacent in the circular arrangement. Rob house at index 1 (value = 3).

Example 2:

Input: houses = [1, 2, 3, 1] Output: 4 Explanation: Rob house at index 0 (value = 1) and house at index 2 (value = 3). Total = 1 + 3 = 4.

Example 3:

Input: houses = [5] Output: 5 Explanation: Only one house available, rob it for maximum value of 5.