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