Make Array Zero by Subtracting Equal Amounts

EASY

Description

You are given a non-negative integer array nums. In one operation, you must:

Choose a positive integer x such that x is less than or equal to the smallest non-zero element in nums.
Subtract x from every positive element in nums.

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 <= 100
0 <= nums[i] <= 100

Approaches

Checkout 4 different approaches to solve Make Array Zero by Subtracting Equal Amounts. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Simulation

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 operations counter 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 x is found, increment the operations counter.
Then, iterate through the array again. For every element nums[i] that is greater than 0, subtract x from it: nums[i] = nums[i] - x.
After the loop terminates, return the operations count.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we modify the array in-place and use only a few variables for tracking.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Make Array Zero by Subtracting Equal Amounts. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Make Array Zero by Subtracting Equal Amounts

Algorithms:

Sorting

Patterns:

Greedy

Data Structures:

ArrayHash TableHeap (Priority Queue)