Problem of The Day: House Robber IV

Problem Statement

Dynamic Programming Approach [TLE]

class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        @cache
        def dfs(i, curr, k):
            if k == 0:
                return curr
            if i >= len(nums):
                return float('inf')

            include = dfs(i + 2, max(curr, nums[i]), k - 1)
            exclude = dfs(i + 1, curr, k)
            return min(include, exclude)

        res = float('inf')
        for i in range(len(nums)):
            val = dfs(i, 0, k)
            res = min(res, val)
        return res

Editorial Solution

Binary Search

class Solution:
    def minCapability(self, nums, k):
        # Store the maximum nums value in maxReward.
        min_reward, max_reward = 1, max(nums)
        total_houses = len(nums)

        # Use binary search to find the minimum reward possible.
        while min_reward < max_reward:
            mid_reward = (min_reward + max_reward) // 2
            possible_thefts = 0

            index = 0
            while index < total_houses:
                if nums[index] <= mid_reward:
                    possible_thefts += 1
                    index += 2  # Skip the next house to maintain the non-adjacent condition
                else:
                    index += 1

            if possible_thefts >= k:
                max_reward = mid_reward
            else:
                min_reward = mid_reward + 1

        return min_reward