Watch 9 video solutions for Minimum K to Reduce Array Within Limit, a medium level problem involving Array, Binary Search. This walkthrough by Study Placement has 240 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a positive integer array nums.
For a positive integer k, define nonPositive(nums, k) as the minimum number of operations needed to make every element of nums non-positive. In one operation, you can choose an index i and reduce nums[i] by k.
Return an integer denoting the minimum value of k such that nonPositive(nums, k) <= k2.
Example 1:
Input: nums = [3,7,5]
Output: 3
Explanation:
When k = 3, nonPositive(nums, k) = 6 <= k2.
nums[0] = 3 one time. nums[0] becomes 3 - 3 = 0.nums[1] = 7 three times. nums[1] becomes 7 - 3 - 3 - 3 = -2.nums[2] = 5 two times. nums[2] becomes 5 - 3 - 3 = -1.Example 2:
Input: nums = [1]
Output: 1
Explanation:
When k = 1, nonPositive(nums, k) = 1 <= k2.
nums[0] = 1 one time. nums[0] becomes 1 - 1 = 0.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You are given an integer array and a limit on the number of operations allowed to reduce it. Each operation reduces an element by up to k. The goal is to find the minimum value of k such that the entire array can be reduced within the allowed limit of operations.
Approach 1: Linear Search on k (O(n * M) time, O(1) space)
Start from k = 1 and keep increasing it until the required number of operations becomes less than or equal to the allowed limit. For each candidate k, iterate through the array and compute how many operations each element requires using a ceiling-style division like ceil(nums[i] / k). Sum the operations and check if it stays within the limit. This method is easy to reason about but inefficient because k may need to be tested up to the maximum value in the array.
Approach 2: Binary Search on k (O(n log M) time, O(1) space)
The key observation is monotonic behavior: if a certain k allows the array to be reduced within the limit, any larger k will also work because each operation removes more value. This makes the answer searchable using Binary Search. Set the search range from 1 to max(nums). For each midpoint k, iterate through the array and calculate the total operations required using (num + k - 1) / k. If the total operations exceed the limit, increase k. Otherwise, try a smaller k to find the minimum valid value.
The feasibility check runs in O(n), and binary search performs log M iterations where M is the maximum element in the array. This produces an overall complexity of O(n log M) with constant extra space.
Recommended for interviews: The Binary Search approach. Interviewers expect you to recognize the monotonic relationship between k and the number of operations required. Demonstrating the brute-force reasoning first shows understanding of the constraint, while converting it into a binary search over the answer shows strong problem-solving skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Search on k | O(n * M) | O(1) | Useful for reasoning about the problem or when the maximum value in the array is very small |
| Binary Search on Answer | O(n log M) | O(1) | General case; optimal when k lies within a large numeric range |