House Robber - Practice Coding Problems

House Robber - Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 Case

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

› Output: 12

💡 Note: Rob houses 0, 2, and 4: 2 + 9 + 1 = 12. Cannot rob adjacent houses 1 and 3.

Example 2 — Choose Larger Adjacent

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

› Output: 4

💡 Note: Rob houses 1 and 3: 2 + 3 = 5, but better to rob houses 0 and 2: 1 + 3 = 4. Actually optimal is 2 + 1 = 4 (houses 1,3).

Example 3 — Single House

$ Input: nums = [5]

› Output: 5

💡 Note: Only one house available, rob it for maximum of 5.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of house values with adjacency constraint

Process

Choose non-adjacent houses for maximum sum

Output

Maximum money that can be robbed

Key Takeaway

🎯 Key Insight: At each house, choose max of (rob current + best two houses ago) vs (skip current, keep previous best)

Asked in

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

The key insight is that for each house, we choose the maximum between robbing it (current money + best from i-2) or skipping it (best from i-1). Best approach is space-optimized DP using two variables. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Recursion with Memoization	O(n)	O(n)	Cache recursive results to avoid recomputation
Dynamic Programming (Bottom-Up)	O(n)	O(n)	Build solution iteratively using DP array
Space-Optimized DP	O(n)	O(1)	Track only previous two values instead of full DP array
Brute Force Recursion	O(2ⁿ)	O(n)	Try all combinations of non-adjacent houses recursively

Recursion with Memoization — Algorithm Steps

Use a memo array to cache results
Before recursing, check if result already computed
Store result in memo before returning
Each index computed only once

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate

Solve subproblem and store result

Cache

Save result in memo table

Reuse

Return cached result for repeated subproblems

Code -

solution.c — C

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

int memo[1000];
int memo_set[1000];

int robFrom(int* nums, int numsSize, int i) {
    if (i >= numsSize) return 0;
    if (memo_set[i]) return memo[i];
    
    // Choice 1: rob current house + rob from i+2
    int robCurrent = nums[i] + robFrom(nums, numsSize, i + 2);
    // Choice 2: skip current house, rob from i+1
    int skipCurrent = robFrom(nums, numsSize, i + 1);
    
    memo[i] = robCurrent > skipCurrent ? robCurrent : skipCurrent;
    memo_set[i] = 1;
    return memo[i];
}

int solution(int* nums, int numsSize) {
    memset(memo_set, 0, sizeof(memo_set));
    return robFrom(nums, numsSize, 0);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each house is processed exactly once due to memoization

✓ Linear Growth

Space Complexity

O(n)

Memo array of size n plus recursion call stack of depth n

⚡ Linearithmic Space

67.9K Views

High Frequency

~15 min Avg. Time

1.9K 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

Recursion with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler