[Leetcode] 2560. House Robber IV

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

initial

So previously i solved a BS problem. RMB bs mid is literally our guess answer so in this case, it is the threshold value.

Then i was wondering how to impl greedy function. My initial approach was checking idx and idx+2 and seeing if the max of those 2 are less than our guess threshold value. But we dont have to compare idx+2, which reduces our search range cuz we have to do idx<n-2, cuz

Why max(nums[idx], nums[idx+2]) <= guess is wrong for House Robber IV:

This condition fundamentally misinterprets the "capability" rule. The capability applies to each individual house you rob. You don't need to consider nums[idx+2] to decide about nums[idx].

If nums[idx] itself is within your guess (e.g., nums[idx]=3, guess=5), you can rob it, even if nums[idx+2] is very high (e.g., nums[idx+2]=100). The 100 would just mean you can't rob nums[idx+2] with a guess of 5, but it doesn't stop you from robbing nums[idx].

another issue was setting the right value. I set right as max(nums) but if nums = [2,2], then our mid value can never be 2. Instead either put max(nums)+1 or just int(10e9) to be safe.

sol

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        n=len(nums)
        left,right=0,int(10e9)

        def greedy(guess):
            nonlocal n,nums
            idx=0
            count=0
            while idx<n:
                if nums[idx]<=guess:
                    count+=1
                    idx+=2
                else:
                    idx+=1
            return count

        ans = 0
        while left<right:
            mid=left+(right-left)//2
            # greedy should return number of houses to be robbed
            if greedy(mid)>=k:
                right=mid
                ans=mid
            else:
                left=mid+1
        return ans

        

complexity

n time
1 space