2560. House Robber IV

Problem Description

In this problem, we are considering a street lined with consecutive houses, each containing a certain amount of money. A robber aims to steal money from these houses, but with one condition: they are not willing to rob two adjacent houses. This constraint is dictated by the need to minimize the risk of getting caught. Additionally, there is a requirement that the robber must steal from at least k houses. The robber's "capability" is defined as the maximum amount of money stolen from a single house during the heist.

We are given an array of integers nums, where nums[i] represents the amount of money in the ith house. We also have an integer k, which represents the minimum number of houses from which the robber must steal.

Our task is to calculate the minimum "capability" of the robber to achieve the heist of at least k houses. In other words, among all the possible strategies to rob at least k houses while avoiding adjacent homes, we want to find the one that involves the robber stealing the least amount of money from any single house they choose to rob. This will be the smallest maximum amount of money taken from one house in any valid robbing strategy.

Intuition

The intuition behind the solution is to use binary search along with a custom feasibility function to find the desired minimum capability. The first insight is that if the robber can complete the heist with a certain capability, they can also complete it with any higher capability. This makes the problem a good candidate for binary search, where the answer is the smallest capability that allows the robber to rob at least k non-adjacent houses.

Here's the step-by-step approach:

Define a feasibility function f(x) that takes a capability value x and returns True if it's possible for the robber to complete the heist with capability x, or False otherwise. This function simulates the robber's actions, stealing from non-adjacent houses with values less than or equal to 'x' until they have reached the target of k houses.
Apply binary search to find the minimum x for which f(x) is True. The search space is from 0 to the maximum amount in any house (inclusive), as the robber could potentially need to rob the house with the most money if k equals the total number of houses.
The feasibility function keeps two variables: a counter cnt for the number of successfully robbed houses, and j to track the index of the last house the robber stole from.
For each house, if its value is greater than x or it's adjacent to the last robbed house (index j), the robber skips it.
Whenever a house is eligible (it satisfies the conditions and is not next to the last robbed house), increment cnt and update j to the current house's index.
If cnt reaches at least k, f(x) returns True, indicating that robbing at least k houses is feasible with the current capability x.
Use Python's bisect_left function with a range of capabilities and the feasibility function as the key. This will find the leftmost index where f(x) is True, which corresponds to the minimum capability required.

By using binary search, we efficiently narrow down the minimum capability required rather than checking every possible capability value.

Learn more about Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]["jm", "kn", "lo"]["jklmnp"]["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know

Solution Approach

The solution is implemented in Python and utilizes a binary search algorithm. Binary search is a highly efficient algorithm used to find an element in a sorted sequence by repeatedly dividing the search interval in half.

Here’s a detailed explanation of the solution implementation:

Binary Search Rationale: Since we are looking for the minimum capability, we set up a binary search over a range of possible capabilities, starting from 0 to max(nums). Binary search works on a sorted sequence, and while capability values aren't inherently sorted, their feasibility is monotonically increasing: if it's possible to rob at least k houses with capability x, it's possible with any x' > x as well.
Feasibility Function f(x): This function takes a capability value x as input and determines whether it is possible to rob at least k houses without robbing adjacent ones and not exceeding capability x. The function iterates over all the houses, maintaining a count cnt of houses robbed and an index j of the last house robbed to enforce the non-adjacent constraint.
Conditional House Selection: While iterating through the houses, two conditions must be checked for each house to decide whether it can be robbed:
- Its value is less than or equal to the capability x.
- It is not adjacent to the last house robbed, which is checked by comparing the current index i with j + 1.
Incrementing and Checking Count: Whenever a house meets the above conditions, we increment cnt and update j to the current index. If cnt becomes greater or equal to k, f(x) returns True, signaling that this capability level is feasible.
Binary Search Execution: Python's bisect_left function is used to find the smallest index in the range [0, max(nums) + 1) where f(x) returns True. Here, bisect_left(range(max(nums) + 1), True, key=f) is searching for the position to insert True in a sorted sequence of boolean values obtained by applying f(x) on each x within the range so that the list remains sorted. Since f(x) returns True for all x greater than or equal to the minimum capability, bisect_left effectively finds the smallest such x.
Time Complexity: The time complexity of this solution is O(n log m), where n is the number of houses and m is the maximum amount of money in any house. The function f(x) takes O(n) time per check, and the binary search requires O(log m) checks.

The use of binary search greatly optimizes the search process compared to a brute-force approach, which would have been significantly slower and less efficient.

The provided Python solution leverages the algorithmic strength of binary search in combination with a custom-designed feasibility checker to solve this problem of optimizing the robber's capability within the given constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Suppose we are given the following array of integers representing the amounts of money in the houses and a minimum number of houses k the robber needs to steal from:

1nums = [2, 3, 1, 1, 5, 1, 2]
2k = 3

Our task is to find the minimum "capability" for the robber so that they can rob at least k non-adjacent houses.

Step 1: Binary Search Rationale

We initiate a binary search for capabilities ranging from 0 to the maximum value in nums, which is 5 in this case. Hence, our search space is 0 to 5.

Step 2: Feasibility Function `f(x)`

The feasibility function checks if the robber can rob k non-adjacent houses with a capability x. Let us see how this function works with an example capability of x = 3.

Step 3: Conditional House Selection

When iterating through nums using the feasibility function with x = 3, the robber can rob houses with value less than or equal to 3 and must skip adjacent houses.

House 0: Value is 2 (≤ 3), robber can steal from this house.
House 1: Value is 3 (≤ 3), but it's adjacent to House 0, so the robber skips this house.
House 2: Value is 1 (≤ 3), and not adjacent to the last robbed house (House 0), so the robber can steal.
House 3: Value is 1 (≤ 3), but adjacent to House 2, so it's skipped.
House 4: Value is 5 (> 3), so this house can't be robbed with capability of 3.
House 5: Value is 1 (≤ 3), and not adjacent to the last robbed house (House 2), so the robber can steal.

After this process, the robber has stolen from 3 houses (0, 2, and 5), which means f(3) = True.

Step 4: Incrementing and Checking Count

We check if at least k houses can be robbed without exceeding the capability x. Since f(3) returned True, we can proceed with the binary search to see if there's a lower capability that still allows for k houses to be robbed.

Step 5: Binary Search Execution

Using the bisect_left function, we find that the smallest capability where f(x) returns True is actually 2, because the robber could steal from houses 0, 2, and 5 with amounts of 2, 1, and 1, respectively, satisfying the requirement to steal from at least k = 3 houses without robbing adjacent houses.

Step 6: Time Complexity

The time complexity of this operation for our list nums is O(n log m) where n is 7 and m is 5, resulting from the binary search operation and feasibility checks for each capability value.

By applying this algorithm, we have efficiently determined the minimum "capability" for the robber, allowing them to complete their heist according to the given constraints. In our example, the minimum capability is 2. This is the least amount of money that the robber would need to steal from any single house in their strategy to rob at least k = 3 non-adjacent houses.

Solution Implementation

1from typing import List
2from bisect import bisect_left
3
4class Solution:
5    # This function aims to find the minimum capability required to form k pairs
6    def minCapability(self, nums: List[int], k: int) -> int:
7      
8        # The inner function 'is_feasible' checks if a given capability 'capability'
9        # is sufficient to form at least k pairs.
10        def is_feasible(capability):
11            count, last_used_index = 0, -2  # Initialize counters
12            for current_index, value in enumerate(nums):
13                # Skip if the value is greater than the capability or if the element
14                # is right after the previously used element (to ensure non-adjacency).
15                if value > capability or current_index == last_used_index + 1:
16                    continue
17                # If neither condition is met, increment the count
18                # and update 'last_used_index'.
19                count += 1
20                last_used_index = current_index
21            # Check if the capability is sufficient to form k pairs.
22            return count >= k
23
24        # Perform a binary search over the range [0, max(nums) + 1),
25        # using the 'is_feasible' function as the key.
26        # The 'bisect_left' will find the leftmost value in the range
27        # where 'is_feasible' returns True (i.e., the minimum capability).
28        return bisect_left(range(max(nums) + 1), True, key=is_feasible)
29

1class Solution {
2
3    // Determine the minimum capability to partition the array in such a way that
4    // the sum of each sub-array is less than or equal to k
5    public int minCapability(int[] nums, int k) {
6        // Start with the least possible capability
7        int left = 0;
8        // Set an upper limit for the search space, assuming the max value according to problem constraints
9        int right = (int) 1e9;
10
11        // Perform a binary search to find the minimum capability
12        while (left < right) {
13            // Get the midpoint of the current search space
14            int mid = (left + right) >> 1;
15
16            // Check if the current capability can achieve the required partition
17            if (calculatePartitionCount(nums, mid) >= k) {
18                // If it qualifies, search the lower half to find a smaller capability
19                right = mid;
20            } else {
21                // Otherwise, search the upper half
22                left = mid + 1;
23            }
24        }
25
26        // left is now the minimum capability that can achieve the required partition
27        return left;
28    }
29
30    // Helper method to calculate the number of partitions formed by capability x
31    private int calculatePartitionCount(int[] nums, int x) {
32        int count = 0; // Initialize the partition count
33        int lastPartitionIndex = -2; // Initialize the index of the last partition start
34
35        // Iterate over the array
36        for (int i = 0; i < nums.length; ++i) {
37            // Skip if the current number exceeds the capability or is the next immediate number after the last partition
38            if (nums[i] > x || i == lastPartitionIndex + 1) {
39                continue;
40            }
41            // Increment the partition count and update lastPartitionIndex
42            ++count;
43            lastPartitionIndex = i;
44        }
45
46        // Return the total number of partitions that can be made with capability x
47        return count;
48    }
49}
50

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to find the minimum capability needed to meet the condition.
7    int minCapability(std::vector<int>& nums, int k) {
8        // Lambda function to check if a given capability meets the condition.
9        auto isCapable = [&](int capability) {
10            int count = 0; // Initialize the count of qualified elements.
11            int prevIndex = -2; // Initialize the previous index (-2 is out of possible index range).
12
13            // Iterate through the numbers in the vector.
14            for (int i = 0; i < nums.size(); ++i) {
15                // Skip the number if it's greater than the capability or 
16                // if it's the direct neighbor of the previously considered element.
17                if (nums[i] > capability || i == prevIndex + 1) {
18                    continue;
19                }
20                // Increment the count of elements and update the previous index.
21                ++count;
22                prevIndex = i;
23            }
24            // Return true if the count is greater than or equal to k.
25            return count >= k;
26        };
27      
28        // Binary search setup:
29        // Set the left boundary of the search to 0.
30        int left = 0;
31        // Find the maximum number in the vector and use it as the right boundary.
32        int right = *std::max_element(nums.begin(), nums.end());
33
34        // Perform binary search.
35        while (left < right) {
36            // Calculate the middle value between left and right.
37            int mid = (left + right) >> 1;
38            // If the current capability meets the condition, adjust the right boundary.
39            if (isCapable(mid)) {
40                right = mid;
41            } else {
42                // Otherwise, adjust the left boundary.
43                left = mid + 1;
44            }
45        }
46        // After exiting the loop, the smallest capability is found.
47        return left;
48    }
49};
50

1/**
2 * Determine the minimum capability required to select at least k elements,
3 * such that every two selected ones have at least one other element between them.
4 *
5 * @param capabilities - Array of capabilities.
6 * @param k - Number of elements to select.
7 * @return - The minimum capability required.
8 */
9function minCapability(capabilities: number[], k: number): number {
10  /**
11   * Helper function to determine if it's possible to select k elements
12   * given the constraint of at least one element between selected ones.
13   *
14   * @param maxCapability - The maximum capability to allow for selection.
15   * @return - True if at least k elements can be selected, false otherwise.
16   */
17  const canSelectKElements = (maxCapability: number): boolean => {
18    let count = 0; // Count of elements selected
19    let lastSelectedIndex = -2; // Index of last selected element
20
21    // Loop through all elements to determine if we can select them
22    for (let i = 0; i < capabilities.length; ++i) {
23      // Check if the current element can be selected (has desired capability and has gap)
24      if (capabilities[i] <= maxCapability && i - lastSelectedIndex > 1) {
25        ++count; // Increase the selected count
26        lastSelectedIndex = i; // Update the index of last selected element
27      }
28    }
29
30    // If we have selected at least k elements, return true.
31    return count >= k;
32  };
33
34  let left = 1;
35  // Find the element with the maximum capability.
36  let right = Math.max(...capabilities);
37
38  // Binary search to find the minimum capability required.
39  while (left < right) {
40    // Take the middle of the current range as the candidate capability.
41    const mid = (left + right) >> 1; // Equivalent to Math.floor((left + right) / 2)
42
43    // Use the helper function to check if mid can be a solution.
44    if (canSelectKElements(mid)) {
45      // We can select k elements with the mid capability, try lower capabilities.
46      right = mid;
47    } else {
48      // We cannot select k elements with the mid capability, try higher capabilities.
49      left = mid + 1;
50    }
51  }
52
53  // Return the lowest capability found by the binary search.
54  return left;
55}
56

Not Sure What to Study? Take the 2-min Quiz：

Time and Space Complexity

Time Complexity

The given Python function minCapability uses binary search through the bisect_left function to find the minimum capability required. It applies a helper function f as a key which processes the nums list on each iteration.

The bisect_left function performs a binary search over a range of size max(nums) + 1, which involves O(log(Max)) iterations, where Max is the maximum element in nums.
Within each binary search iteration, the helper function f performs a linear scan over the nums list of size n, to check how many elements can be skipped without exceeding capability x. The time complexity for this will be O(n).

Combining these two, the overall time complexity will be O(n * log(Max)), where n is the number of elements in nums, and Max is the maximum element in nums.

Space Complexity

The space complexity of the minCapability function is O(1) assuming that the list nums is given and does not count towards the space complexity (as it's an input). There are no additional data structures used that grow with the input size. The variables cnt, j, i, and v use a constant amount of space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

TrueFalse

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2560. House Robber IV

Problem Description

Intuition

Solution Approach

Example Walkthrough

Step 1: Binary Search Rationale

Step 2: Feasibility Function f(x)

Step 3: Conditional House Selection

Step 4: Incrementing and Checking Count

Step 5: Binary Search Execution

Step 6: Time Complexity

Step 2: Feasibility Function `f(x)`