Make Array Zero by Subtracting Equal Amounts

easy heap greedy hash table

Problem

You are given a non-negative array nums. In one operation you pick a positive x that is at most the smallest non-zero element, then subtract x from every positive element. Return the minimum number of operations needed to make every element 0.

It is always optimal to set x to the current smallest non-zero value: that turns all of those minimum elements into 0 at once. So the answer is simply the count of distinct non-zero values — each distinct level is cleared by exactly one operation. A min-heap lets us peel those levels off in increasing order.

Inputnums = [1, 5, 0, 3, 5]

Output3

Subtract 1 → [0,4,0,2,4], subtract 2 → [0,2,0,0,2], subtract 2 → all 0. The distinct non-zero values are {1, 3, 5}, so 3 operations.

nums (comma-separated, 0..100)

def minimumOperations(nums):
    import heapq
    # Push every non-zero value into a min-heap.
    heap = [n for n in nums if n > 0]
    heapq.heapify(heap)
    ops = 0          # operations performed
    base = 0         # total amount subtracted so far
    while heap:
        v = heapq.heappop(heap)   # smallest remaining value
        if v > base:              # a new non-zero level
            ops += 1              # one operation clears it
            base = v              # everything now reduced to v
    return ops

function minimumOperations(nums) {
  // Collect non-zero values and sort to mimic a min-heap pop order.
  const heap = nums.filter(n => n > 0).sort((a, b) => a - b);
  let ops = 0;        // operations performed
  let base = 0;       // total amount subtracted so far
  for (const v of heap) {   // pop smallest each time
    if (v > base) {         // a new non-zero level
      ops += 1;            // one operation clears it
      base = v;            // everything now reduced to v
    }
  }
  return ops;
}

int minimumOperations(int[] nums) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int n : nums) if (n > 0) heap.offer(n);  // non-zero values
    int ops = 0;        // operations performed
    int base = 0;       // total amount subtracted so far
    while (!heap.isEmpty()) {
        int v = heap.poll();    // smallest remaining value
        if (v > base) {         // a new non-zero level
            ops += 1;          // one operation clears it
            base = v;          // everything now reduced to v
        }
    }
    return ops;
}

int minimumOperations(vector<int>& nums) {
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int n : nums) if (n > 0) heap.push(n);  // non-zero values
    int ops = 0;        // operations performed
    int base = 0;       // total amount subtracted so far
    while (!heap.empty()) {
        int v = heap.top(); heap.pop();  // smallest remaining value
        if (v > base) {                  // a new non-zero level
            ops += 1;                   // one operation clears it
            base = v;                   // everything now reduced to v
        }
    }
    return ops;
}

Explanation

This is a greedy problem with a clean heap-flavored framing. Each operation subtracts the same amount x from every positive element, and x can be at most the smallest non-zero value. The best move is always to take x equal to that smallest value: it drives all of the current minimum elements to 0 in a single step, and nothing is wasted.

After that operation, every remaining positive element has been reduced by the same amount. So two elements that were equal stay equal, and elements that differed still differ. That means each distinct non-zero value defines its own “level” that gets cleared by exactly one operation. The answer is therefore the number of distinct non-zero values.

We realize this with a min-heap. Push every non-zero element, then pop them in increasing order. We keep a running base = the total amount subtracted so far. When a popped value v is strictly greater than base, it is a brand-new level: we spend one operation and set base = v. Duplicate values pop out equal to base and cost nothing extra.

Example: nums = [1, 5, 0, 3, 5]. The heap holds {1, 3, 5, 5}. Pop 1 > 0 → ops 1, base 1. Pop 3 > 1 → ops 2, base 3. Pop 5 > 3 → ops 3, base 5. Pop 5 = base → no change. Final answer 3.

An equivalent one-liner is to simply count the size of the set of non-zero values, but the heap version makes the “peel off levels in order” intuition explicit and visual.

Time: O(n log n) Space: O(n)