House Robber IV - Practice Coding Problems

House Robber IV - Problem

There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes.

The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.

You are given an integer array nums representing how much money is stashed in each house. More formally, the i^th house from the left has nums[i] dollars.

You are also given an integer k, representing the minimum number of houses the robber will steal from. It is always possible to steal at least k houses.

Return the minimum capability of the robber out of all the possible ways to steal at least k houses.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,7,11,15], k = 1

› Output: 2

💡 Note: We can rob house 0 alone with capability 2, which is the minimum possible

Example 2 — Multiple Houses Required

$ Input: nums = [2,3,5,9], k = 2

› Output: 5

💡 Note: Rob houses [2,5] with capability max(2,5)=5, or houses [3,9] with capability max(3,9)=9. Minimum is 5

Example 3 — Edge Case

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

› Output: 1

💡 Note: Rob only house 0 with value 1, giving capability 1

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ k ≤ (nums.length + 1) / 2

Visualization

Tap to expand

Understanding the Visualization

Input

Array of house values and minimum houses k to rob

Constraint

Cannot rob adjacent houses (security alarms)

Goal

Minimize the maximum house value robbed (capability)

Key Takeaway

🎯 Key Insight: Binary search on the capability value, since if we can rob k houses with capability X, we can also do it with X+1

Asked in

G Google 12 f Facebook 8 a Amazon 15 M Microsoft 10

The key insight is to use binary search on the answer space. If we can rob k houses with capability X, we can also do it with any capability > X. The optimal approach uses binary search on capability values combined with a greedy validation check. Time: O(n log(max-min)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer with Greedy Check	O(n log(max-min))	O(1)	Binary search the capability value, use greedy to check if k houses are possible
Brute Force with Backtracking	O(2^n)	O(n)	Try all possible combinations of non-adjacent houses

Binary Search on Answer with Greedy Check — Algorithm Steps

Step 1: Binary search on capability values from min(nums) to max(nums)
Step 2: For each capability, greedily check if k houses can be robbed
Step 3: Return the minimum valid capability

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search Setup

Search space from min(nums) to max(nums)

Greedy Validation

Check if k houses can be robbed with given capability

Converge Answer

Narrow search until minimum capability found

Code -

solution.c — C

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

int canRob(int* nums, int n, int k, int capability) {
    int count = 0;
    int i = 0;
    while (i < n) {
        if (nums[i] <= capability) {
            count++;
            i += 2; // Skip next house
        } else {
            i++;
        }
    }
    return count >= k;
}

int solution(int* nums, int n, int k) {
    int left = nums[0], right = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < left) left = nums[i];
        if (nums[i] > right) right = nums[i];
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canRob(nums, n, k, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, n, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(max-min))

Binary search runs log(max-min) times, each iteration scans n houses

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables for binary search and greedy check

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 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

Binary Search on Answer with Greedy Check — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler