Make Array Zero by Subtracting Equal Amounts
EasyPrompt
You are given a non-negative integer array nums. In one operation, you must:
- Choose a positive integer
xsuch thatxis less than or equal to the smallest non-zero element innums. - Subtract
xfrom every positive element innums.
Return the minimum number of operations to make every element in nums equal to 0.
Example 1:
Input: nums = [1,5,0,3,5]
Output: 3
Explanation:
In the first operation, choose x = 1. Now, nums = [0,4,0,2,4].
In the second operation, choose x = 2. Now, nums = [0,2,0,0,2].
In the third operation, choose x = 2. Now, nums = [0,0,0,0,0].Example 2:
Input: nums = [0]
Output: 0
Explanation: Each element in nums is already 0 so no operations are needed.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. It repeatedly finds the smallest non-zero element, subtracts it from all positive elements, and counts the operations until all elements become zero.
Algorithm
- Initialize an
operationscounter to 0. - Enter a loop that continues as long as there are positive numbers in the array.
- Inside the loop, first find the smallest positive number, let's call it
x. - If no positive number is found (all are zero), break the loop.
- If a smallest positive number
xis found, increment theoperationscounter. - Then, iterate through the array again. For every element
nums[i]that is greater than 0, subtractxfrom it:nums[i] = nums[i] - x. - After the loop terminates, return the
operationscount.
Walkthrough
This method follows the problem description literally. In each step, it scans the entire array to find the minimum positive element. If one is found, it increments an operation counter and then scans the array again to subtract this minimum value from all positive elements. This process repeats until all elements in the array are zero.
class Solution { public int minimumOperations(int[] nums) { int operations = 0; while (true) { int minPositive = Integer.MAX_VALUE; boolean allZero = true; for (int num : nums) { if (num > 0) { allZero = false; minPositive = Math.min(minPositive, num); } } if (allZero) { break; } operations++; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { nums[i] -= minPositive; } } } return operations; }}Complexity
Time
O(U * N), where N is the length of the array and U is the number of unique positive elements. In each of the U operations, we iterate through the array twice (once to find the minimum, once to subtract), which takes O(N) time.
Space
O(1), as we modify the array in-place and use only a few variables for tracking.
Trade-offs
Pros
Simple to understand and directly follows the problem statement.
Requires no extra space.
Cons
Inefficient due to repeated traversals of the array, leading to a quadratic time complexity in the worst case.
Solutions
Solution
class Solution {public int minimumOperations(int[] nums) { boolean[] s = new boolean[101]; s[0] = true; int ans = 0; for (int x : nums) { if (!s[x]) { ++ans; s[x] = true; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.