# Make Array Zero by Subtracting Equal Amounts
**Difficulty:** EASY
[External](https://leetcode.com/problems/make-array-zero-by-subtracting-equal-amounts)
Canonical: https://scaleengineer.com/dsa/problems/make-array-zero-by-subtracting-equal-amounts
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
---
## Problem
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
## 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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Sorting-based Approach
This approach improves upon the simulation by first sorting the array. Sorting allows us to process the numbers in increasing order, which simplifies the logic of finding the next smallest element to subtract without repeatedly scanning the array.
**Time:** O(N log N), dominated by the sorting step. The subsequent loop is O(N). · **Space:** O(log N) or O(N), depending on the sort implementation's space requirements. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which has an average space complexity of O(log N).
**Pros:** More efficient than the brute-force simulation.; Still conceptually linked to the simulation process but optimized.
**Cons:** The sorting step is the bottleneck, making it slower than linear-time solutions.
### Explanation
The core idea is that after sorting, we can iterate through the array once. We keep track of the total amount that has been subtracted from all numbers so far. For each number, we check its effective value after subtraction. If it's positive, it represents a new unique value that needs to be zeroed out, so we perform an "operation" and update the total subtracted amount.

```java
import java.util.Arrays;

class Solution {
    public int minimumOperations(int[] nums) {
        Arrays.sort(nums);
        int operations = 0;
        int totalSubtracted = 0;
        for (int num : nums) {
            if (num > 0 && num > totalSubtracted) {
                operations++;
                totalSubtracted = num;
            }
        }
        return operations;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize `operations = 0` and `totalSubtracted = 0`.
- Iterate through the sorted array `nums`.
- For each `num`, calculate its current value: `currentVal = num - totalSubtracted`.
- If `currentVal > 0`, it means we've encountered a new smallest positive number.
  - Increment `operations`.
  - Add `currentVal` to `totalSubtracted`. This simulates subtracting this new smallest value from all subsequent larger numbers.
- If `currentVal` is 0, it means this number has already been reduced to zero by previous operations, so we do nothing.
- Return `operations`.

## Counting Unique Positives with a HashSet
A key insight is that each operation effectively eliminates one unique positive value from the set of numbers present in the array. Therefore, the minimum number of operations is simply the count of unique positive numbers in the initial array. This approach uses a HashSet to efficiently count these unique positive numbers.
**Time:** O(N), where N is the length of the array. We iterate through the array once, and each HashSet insertion takes O(1) on average. · **Space:** O(U), where U is the number of unique positive elements. In the worst case, U can be up to N, so the space complexity is O(N).
**Pros:** Simple, elegant, and has an optimal time complexity.; Works for any range of integer values, not just small ones.
**Cons:** Uses extra space for the HashSet, which might be slightly less efficient in terms of memory and constant factors than a frequency array approach given the problem's constraints.
### Explanation
We can iterate through the array once, adding all positive numbers to a `HashSet`. A `HashSet` automatically handles duplicates; adding an existing element has no effect. The final size of the set gives us the count of unique positive numbers, which is the answer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int minimumOperations(int[] nums) {
        Set<Integer> uniquePositives = new HashSet<>();
        for (int num : nums) {
            if (num > 0) {
                uniquePositives.add(num);
            }
        }
        return uniquePositives.size();
    }
}
```
### Algorithm
- Create an empty `HashSet<Integer>`.
- Iterate through each number `num` in the input array `nums`.
- If `num` is greater than 0, add it to the `HashSet`.
- After the loop, return the size of the `HashSet`.

## Counting Unique Positives with a Boolean Array
This is the most efficient approach, leveraging the constraint that array values are between 0 and 100. It uses a boolean array as a direct-address table (or a simple hash set) to track which positive numbers have been seen, thereby counting the unique ones.
**Time:** O(N), where N is the length of the array. We iterate through the input array once. The size of the `seen` array is constant (101), so it doesn't affect the asymptotic complexity. · **Space:** O(1). We use a boolean array of a fixed size (101), which is constant space.
**Pros:** Optimal time complexity O(N) and optimal constant space complexity O(1).; Very fast in practice due to direct array access with no hashing overhead.
**Cons:** This specific implementation is only possible because of the tight constraints on the values in `nums` (0 to 100). If the numbers could be very large, this approach would be infeasible due to memory limitations.
### Explanation
Since the numbers are small and non-negative, we can use an array to keep track of the unique positive numbers we've encountered. A boolean array of size 101 is sufficient. The index of the array corresponds to a number, and the value indicates whether that number has been seen. We iterate through the input array, and for each new positive number we encounter, we increment a counter and mark that number as seen in our boolean array.

```java
class Solution {
    public int minimumOperations(int[] nums) {
        boolean[] seen = new boolean[101];
        int count = 0;
        for (int num : nums) {
            if (num > 0 && !seen[num]) {
                count++;
                seen[num] = true;
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a boolean array `seen` of size 101, initialized to `false`.
- Initialize `count = 0`.
- Iterate through each number `num` in `nums`.
- If `num > 0` and `seen[num]` is `false`, it's the first time we've seen this positive number.
  - Increment `count`.
  - Mark it as seen: `seen[num] = true`.
- Return `count`.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def minimumOperations(
        self, nums: List[int]) -> int: return len({x for x in nums if x})

```

### CPP

```cpp
class Solution {
public:
  int minimumOperations(vector<int> &nums) {
    bool s[101]{};
    s[0] = true;
    int ans = 0;
    for (int &x : nums) {
      if (!s[x]) {
        ++ans;
        s[x] = true;
      }
    }
    return ans;
  }
};

```