You are given a 0-indexed integer array nums and two integers x and y. In one operation, you must choose an index i such that 0 <= i < nums.length and perform the following:
nums[i] by x.y at all indices except the ith one.Return the minimum number of operations to make all the integers in nums less than or equal to zero.
Example 1:
Input: nums = [3,4,1,7,6], x = 4, y = 2 Output: 3 Explanation: You will need three operations. One of the optimal sequence of operations is: Operation 1: Choose i = 3. Then, nums = [1,2,-1,3,4]. Operation 2: Choose i = 3. Then, nums = [-1,0,-3,-1,2]. Operation 3: Choose i = 4. Then, nums = [-3,-2,-5,-3,-2]. Now, all the numbers in nums are non-positive. Therefore, we return 3.
Example 2:
Input: nums = [1,2,1], x = 2, y = 1 Output: 1 Explanation: We can perform the operation once on i = 1. Then, nums becomes [0,0,0]. All the positive numbers are removed, and therefore, we return 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= y < x <= 109Problem Overview: You have an array of positive integers. In one operation, you choose an index i, decrease nums[i] by x, and decrease every other element by y. The goal is to find the minimum number of operations required so that every value in the array becomes <= 0.
Approach 1: Greedy Simulation with Heap (O(k log n) time, O(n) space)
A direct strategy repeatedly targets the largest remaining value. Each operation gives that element the stronger reduction x while all others get y. A max heap tracks the current largest value after each update. After performing an operation, update the chosen element by subtracting x and subtract y from the rest. This works conceptually but becomes inefficient when the required number of operations k is large because every step requires heap updates and array adjustments. It mainly serves as intuition: the largest elements should receive the stronger reduction.
Approach 2: Binary Search on Operations (O(n log M) time, O(1) space)
The optimal approach treats the number of operations k as the unknown and searches for it using binary search. After k operations, every element automatically loses y * k due to the global decrease. If an element nums[i] is still positive after that baseline reduction, it must have been selected as the main target several times to apply the stronger decrease x.
The extra benefit of selecting an index is actually x - y, because the element would have already lost y in that operation. For each value, compute the remaining amount rem = nums[i] - y * k. If rem > 0, the element needs ceil(rem / (x - y)) targeted operations. Sum these required targeted operations across the array. If the total is less than or equal to k, then k operations are sufficient.
Binary search the smallest k that satisfies this condition. Each feasibility check scans the array once, making the total complexity O(n log M), where M is the upper bound of operations derived from the maximum value in the array.
Recommended for interviews: The Binary Search on Answer method is what interviewers expect. It converts a seemingly greedy process into a monotonic feasibility check, a common pattern when working with array problems that involve minimizing operations. Showing the brute-force simulation demonstrates understanding of the mechanics, but deriving the binary search condition shows stronger algorithmic reasoning.
We notice that if an operation count t can make all numbers less than or equal to 0, then for any t' > t, the operation count t' can also make all numbers less than or equal to 0. Therefore, we can use binary search to find the minimum operation count.
We define the left boundary of the binary search as l=0, and the right boundary as r=max(nums). Each time we perform a binary search, we find the middle value mid=\lfloor\frac{l+r}{2}\rfloor, and then determine whether there exists an operation method that does not exceed mid and makes all numbers less than or equal to 0. If it exists, we update the right boundary r = mid, otherwise, we update the left boundary
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Simulation with Max Heap | O(k log n) | O(n) | Useful for understanding the greedy behavior; impractical when the required operations are large |
| Binary Search on Number of Operations | O(n log M) | O(1) | Optimal approach for large inputs; efficient feasibility check per iteration |
leetcode 2702. Minimum Operations to Make Numbers Non-positive - binary search and notes [hard] • Code-Yao • 1,041 views views
Watch 2 more video solutions →Practice Minimum Operations to Make Numbers Non-positive with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor