House Robber IV

Link: https://leetcode.com/problems/house-robber-iv/

Prompt

• find minimum possible maximum capability
  • the capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed.
• cannot steal adjacent houses
• steal at least k houses

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= k <= (nums.length + 1)/2

Reason

• minimum-maximum problem
• binary search for the minimum capability (mc)
• greedily pick the non-adjacent elements
  • proof:
    • suppose nums[i] <= mc && nums[i+1] <= mc, we are supposed to pick only one from nums[i] and nums[i+1]
    • if we pick nums[i], we will be able to pick any nums[j], where j >= i+2
    • if we pick nums[i+1], we will be able to pick any nums[j], where j >= i+3
    • we will always have more choices if we pick nums[i], so picking the closest next element that <= mc is always optimal
• time complexity: \(O(nlogm)\)
• space complexity: \(O(1)\)

Solution

• left = 0, right = 1e9+1, mid = (left+right)/2
• binary search: for each mid, greedily pick k non-adjacent elements that are less or equal to mid
  • if impossible: left = mid+1
  • if possible: right = mid