Make Array Zero by Subtracting Equal Amounts

Difficulty: Easy | Acceptance: 73.80% | Paid: No Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Simulation

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.

• Examples
• Constraints
• Simulation Approach
• Hash Set Approach
• Sorting Approach
• Priority Queue Approach

Examples

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 is already 0, so no operations are needed.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

Simulation Approach

Intuition Simulate the process by repeatedly finding the minimum non-zero element and subtracting it from all non-zero elements until all elements become zero.

Steps

• Initialize operations count to 0
• While there are non-zero elements in the array:
  • Find the minimum non-zero element
  • Subtract this minimum from all non-zero elements
  • Increment operations count
• Return the operations count

class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        operations = 0
        while True:
            # Find minimum non-zero element
            min_non_zero = float('inf')
            has_non_zero = False
            for num in nums:
                if num > 0:
                    has_non_zero = True
                    min_non_zero = min(min_non_zero, num)
            
            if not has_non_zero:
                break
            
            # Subtract min_non_zero from all non-zero elements
            for i in range(len(nums)):
                if nums[i] > 0:
                    nums[i] -= min_non_zero
            
            operations += 1
        
        return operations

Complexity

• Time: O(n²) in the worst case where n is the length of the array
• Space: O(1)
• Notes: This approach directly simulates the process but is not the most efficient.

Hash Set Approach

Intuition Each unique positive value in the array requires exactly one operation. Therefore, the answer is simply the count of unique non-zero values.

Steps

• Create a hash set to store unique non-zero values
• Iterate through the array and add all non-zero values to the set
• Return the size of the set

class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        # Count unique non-zero values
        unique_non_zero = set()
        for num in nums:
            if num > 0:
                unique_non_zero.add(num)
        return len(unique_non_zero)

Complexity

• Time: O(n) where n is the length of the array
• Space: O(n) for the hash set
• Notes: This is the optimal solution with linear time complexity.

Sorting Approach

Intuition After sorting the array, we can count unique non-zero values by iterating through the sorted array and counting when we encounter a new value.

Steps

• Sort the array
• Iterate through the sorted array
• Count unique non-zero values
• Return the count

class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        nums.sort()
        count = 0
        prev = 0
        
        for num in nums:
            if num > 0 and num != prev:
                count += 1
                prev = num
        
        return count

Complexity

• Time: O(n log n) due to sorting
• Space: O(1) or O(n) depending on the sorting algorithm
• Notes: Sorting adds overhead but can be useful if we need the array sorted for other purposes.

Priority Queue Approach

Intuition Use a min-heap to efficiently get the smallest non-zero element in each operation, simulating the process more efficiently than the naive simulation.

Steps

• Add all non-zero elements to a min-heap
• While the heap is not empty:
  • Get the minimum element
  • If it’s different from the previous minimum, increment operations
  • Update previous minimum
• Return the operations count

import heapq

class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        # Create min-heap with non-zero elements
        heap = [num for num in nums if num > 0]
        heapq.heapify(heap)
        
        operations = 0
        prev = 0
        
        while heap:
            curr = heapq.heappop(heap)
            if curr != prev:
                operations += 1
                prev = curr
        
        return operations

Complexity

• Time: O(n log n) for heap operations
• Space: O(n) for the heap
• Notes: Using a heap is more efficient than naive simulation but still not as optimal as the hash set approach.