House Robber II - Practice Coding Problems

House Robber II - Problem

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.

Input & Output

Example 1 — Basic Circular Case

$ Input: nums = [2,3,2]

› Output: 3

💡 Note: You cannot rob house 0 and 2 (circular neighbors), so rob house 1 with value 3.

Example 2 — Larger Circle

$ Input: nums = [1,2,3,1]

› Output: 4

💡 Note: Rob houses 1 and 3: 2 + 2 = 4 (wait, that's wrong). Actually rob houses 0 and 2: 1 + 3 = 4, but they're circular neighbors. So rob houses 1 and 2 is invalid (adjacent). Best is rob house 2 only for 3. Wait - let me recalculate: Scenario 1 [1,2,3]: best is 1+3=4. Scenario 2 [2,3,1]: best is 2+1=3. So answer is 4.

Example 3 — Single House

$ Input: nums = [5]

› Output: 5

💡 Note: Only one house to rob, return its value.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Circular Setup

Houses arranged in circle with values [2,3,2]

Adjacent Constraint

Cannot rob adjacent houses (including first-last)

Optimal Solution

Rob house 1 with value 3

Key Takeaway

🎯 Key Insight: Transform the circular problem into two linear problems by excluding either the first or last house.

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to split the circular constraint into two linear House Robber problems: one excluding the last house and one excluding the first house. The optimal approach uses dynamic programming with O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible combinations of non-adjacent houses
Memoization - Top-Down DP	O(n)	O(n)	Recursively solve with caching to avoid recomputation
Dynamic Programming - Two Linear Problems	O(n)	O(1)	Split circular problem into two linear House Robber problems

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible subsets of house indices
Step 2: Check each subset to ensure no adjacent houses are selected
Step 3: Calculate sum for each valid subset and return maximum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all possible combinations of houses

Validate

Check if houses are non-adjacent (including circular)

Find Maximum

Return the combination with maximum sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValidSubset(int* indices, int size, int n) {
    if (size == 0) return true;
    
    // Sort indices
    for (int i = 0; i < size-1; i++) {
        for (int j = i+1; j < size; j++) {
            if (indices[i] > indices[j]) {
                int temp = indices[i];
                indices[i] = indices[j];
                indices[j] = temp;
            }
        }
    }
    
    // Check adjacent
    for (int i = 0; i < size-1; i++) {
        if (indices[i+1] - indices[i] == 1) return false;
    }
    
    // Check circular
    bool hasFirst = false, hasLast = false;
    for (int i = 0; i < size; i++) {
        if (indices[i] == 0) hasFirst = true;
        if (indices[i] == n-1) hasLast = true;
    }
    return !(hasFirst && hasLast);
}

int backtrack(int* nums, int n, int index, int* currentSubset, int subsetSize) {
    if (index == n) {
        if (isValidSubset(currentSubset, subsetSize, n)) {
            int sum = 0;
            for (int i = 0; i < subsetSize; i++) {
                sum += nums[currentSubset[i]];
            }
            return sum;
        }
        return 0;
    }
    
    int maxWithout = backtrack(nums, n, index + 1, currentSubset, subsetSize);
    
    currentSubset[subsetSize] = index;
    int maxWith = backtrack(nums, n, index + 1, currentSubset, subsetSize + 1);
    
    return maxWithout > maxWith ? maxWithout : maxWith;
}

int solution(int* nums, int n) {
    if (n == 0) return 0;
    if (n == 1) return nums[0];
    if (n == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
    
    int* subset = (int*)malloc(n * sizeof(int));
    int result = backtrack(nums, n, 0, subset, 0);
    free(subset);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Generate 2^n subsets and check each one

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

28.4K Views

High Frequency

~25 min Avg. Time

982 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler