Skip to content

← leetcode

House Robber IV

· Medium

LeetCode problem 2560

Quite similar to yesterday's problem, as you are meant to binary search the capability of the robber, and to see if it is valid or not.

You basically just:

  • initialize left and right as the min_element and max_element inside nums
  • binary search for the minimum capability that satisfies all the question constraints

code

class Solution {
public:
    int minCapability(vector<int>& nums, int k) {
        int left = *min_element(nums.begin(), nums.end());
        int right = *max_element(nums.begin(), nums.end());
        int ans;
        while (left <= right) {
            int mid = left - (left - right)/2;

            int count = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid) {
                    ++count;
                    ++i;
                    if (count == k) break;
                }
            }
            if (count == k) {
                ans = mid;
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }
};

complexity

  • Time: O(n log (m)) if n = nums.size() and m = max(nums)
  • Space: O(1)

learnings

  • just remember to have binary search in your arsenal whenever you need to maximize the minimum or minimize the maximum