2357. Make Array Zero by Subtracting Equal Amounts Solution

The 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

Approach overview

Problem Overview: You are given an integer array nums. In one operation, choose a positive integer x that is less than or equal to the smallest non‑zero element and subtract x from every positive element in the array. The goal is to count how many operations are required to make every element equal to zero.

Approach 1: Count Unique Non-Zero Elements (O(n) time, O(n) space)

The key observation is that each operation removes one distinct positive value level from the array. If the array contains values like [1,3,5], the operations correspond to subtracting the smallest remaining positive number each time, effectively collapsing the array level by level. That means the total operations equal the number of distinct non-zero values. You iterate through the array, insert every positive value into a set, and return the size of that set. This approach relies on fast hash lookups and avoids simulation entirely. It is the most efficient solution and directly leverages properties of array traversal and hash table uniqueness.

Approach 2: Sort and Count Changes (O(n log n) time, O(1) extra space)

Another way to view the problem is through ordering. After sorting the array, identical numbers appear together and increasing values represent new subtraction levels. Traverse the sorted array and count how many times the value changes from one positive number to a larger one. Each change represents a new operation because you must subtract the next smallest remaining value. Skip zeros at the beginning, then increment the operation counter whenever nums[i] > nums[i-1]. This method uses sorting to simplify the logic and works well when in-place processing is preferred.

Recommended for interviews: The unique non-zero count approach is the cleanest and runs in linear time. Interviewers expect candidates to recognize the greedy insight that each distinct positive value represents one subtraction round. The sorting approach still demonstrates good reasoning about value transitions but has higher time complexity due to sorting.

Approach 1: Approach 1: Count Unique Non-Zero Elements

This approach is based on the observation that the number of operations required to make all elements zero is equal to the number of unique non-zero elements in the array. This is because, in each operation, we can choose a different positive integer, which effectively removes that integer from all the non-zero elements until all are reduced to zero.

Python

def makeArrayZero(nums):
    uniqueNonZero = {num for num in nums if num > 0}
    return len(uniqueNonZero)

nums = [1, 5, 0, 3, 5]
print(makeArrayZero(nums))

Java

import java.util.HashSet;
import java.util.Set;
class Solution {
    public int makeArrayZero(int[] nums) {
        Set<Integer> uniqueNonZero = new HashSet<>();
        for (int num : nums) {
            if (num > 0) {
                uniqueNonZero.add(num);
            }
        }
        return uniqueNonZero.size();
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 5, 0, 3, 5};
        System.out.println(sol.makeArrayZero(nums));
    }
}

C++

#include <iostream>
#include <unordered_set>
using namespace std;
int makeArrayZero(vector<int>& nums) {
    unordered_set<int> uniqueNonZero;
    for (int num : nums) {
        if (num > 0) {
            uniqueNonZero.insert(num);
        }
    }
    return uniqueNonZero.size();
}

int main() {
    vector<int> nums = {1, 5, 0, 3, 5};
    cout << makeArrayZero(nums) << endl;
    return 0;
}

JavaScript

function makeArrayZero(nums) {
    const uniqueNonZero = new Set();
    for (const num of nums) {
        if (num > 0) {
            uniqueNonZero.add(num);
        }
    }
    return uniqueNonZero.size;
}

const nums = [1, 5, 0, 3, 5];
console.log(makeArrayZero(nums));

#include <stdio.h>
int makeArrayZero(int* nums, int numsSize) {
    int uniqueNonZero[101] = {0};
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] > 0) {
            uniqueNonZero[nums[i]] = 1;
        }
    }
    int count = 0;
    for (int i = 1; i <= 100; i++) {
        if (uniqueNonZero[i]) {
            count++;
        }
    }
    return count;
}

int main() {
    int nums[] = {1, 5, 0, 3, 5};
    int result = makeArrayZero(nums, sizeof(nums)/sizeof(nums[0]));
    printf("%d\n", result);
    return 0;
}

using System;
using System.Collections.Generic;
class Solution {
    public int MakeArrayZero(int[] nums) {
        HashSet<int> uniqueNonZero = new HashSet<int>();
        foreach (int num in nums) {
            if (num > 0) {
                uniqueNonZero.Add(num);
            }
        }
        return uniqueNonZero.Count;
    }
    static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 5, 0, 3, 5};
        Console.WriteLine(sol.MakeArrayZero(nums));
    }
}

We use a set comprehension to collect unique non-zero numbers and return its length which gives us the operations needed.

Complexity

Time Complexity: O(n).
Space Complexity: O(n) due to Python set holding unique numbers.

Try this approach in the editor

Approach 2: Approach 2: Sort and Count Changes

In this approach, we sort the array and traverse it while counting the transitions from one unique non-zero element to the next, which will ultimately give us the number of operations required.

Python

def makeArrayZero(nums):
    nums.sort()
    ops = 0
    for i in range(len(nums)):
        if i == 0 and nums[i] > 0:
            ops += 1
        elif i > 0 and nums[i] > 0 and nums[i] != nums[i - 1]:
            ops += 1
    return ops

nums = [1, 5, 0, 3, 5]
print(makeArrayZero(nums))

Java

import java.util.Arrays;
class Solution {
    public int makeArrayZero(int[] nums) {
        Arrays.sort(nums);
        int ops = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0 && nums[i] > 0) {
                ops++;
            } else if (i > 0 && nums[i] > 0 && nums[i] != nums[i - 1]) {
                ops++;
            }
        }
        return ops;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 5, 0, 3, 5};
        System.out.println(sol.makeArrayZero(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int makeArrayZero(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int ops = 0;
    for (size_t i = 0; i < nums.size(); i++) {
        if (i == 0 && nums[i] > 0) {
            ops++;
        } else if (i > 0 && nums[i] > 0 && nums[i] != nums[i - 1]) {
            ops++;
        }
    }
    return ops;
}

int main() {
    vector<int> nums = {1, 5, 0, 3, 5};
    cout << makeArrayZero(nums) << endl;
    return 0;
}

JavaScript

function makeArrayZero(nums) {
    nums.sort((a, b) => a - b);
    let ops = 0;
    for (let i = 0; i < nums.length; i++) {
        if (i === 0 && nums[i] > 0) {
            ops++;
        } else if (i > 0 && nums[i] > 0 && nums[i] !== nums[i - 1]) {
            ops++;
        }
    }
    return ops;
}

const nums = [1, 5, 0, 3, 5];
console.log(makeArrayZero(nums));

#include <stdio.h>
#include <stdlib.h>
int compare(const void * a, const void * b) {
    return (*(int*)a - *(int*)b);
}
int makeArrayZero(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int ops = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i == 0 && nums[i] > 0) {
            ops++;
        } else if (i > 0 && nums[i] > 0 && nums[i] != nums[i - 1]) {
            ops++;
        }
    }
    return ops;
}

int main() {
    int nums[] = {1, 5, 0, 3, 5};
    int result = makeArrayZero(nums, sizeof(nums)/sizeof(nums[0]));
    printf("%d\n", result);
    return 0;
}

using System;
class Solution {
    public int MakeArrayZero(int[] nums) {
        Array.Sort(nums);
        int ops = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i == 0 && nums[i] > 0) {
                ops++;
            } else if (i > 0 && nums[i] > 0 && nums[i] != nums[i - 1]) {
                ops++;
            }
        }
        return ops;
    }
    static void Main(string[] args) {
        Solution sol = new Solution();
        int[] nums = {1, 5, 0, 3, 5};
        Console.WriteLine(sol.MakeArrayZero(nums));
    }
}

Sort the array, iterate it, and count transitions between unique positive numbers to compute operations needed.

Complexity

Time Complexity: O(n log n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Hash Table or Array

We observe that in each operation, all identical nonzero elements in the array nums can be reduced to 0. Therefore, we only need to count the number of distinct nonzero elements in nums, which is the minimum number of operations required. To count the distinct nonzero elements, we can use a hash table or an array.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

TypeScript

function minimumOperations(nums: number[]): number {
    const s = new Set(nums);
    s.delete(0);
    return s.size;
}

func minimumOperations(nums []int) (ans int) {
	s := [101]bool{true}
	for _, x := range nums {
		if !s[x] {
			s[x] = true
			ans++
		}
	}
	return
}

Rust

use std::collections::HashSet;
impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        let mut s = nums.iter().collect::<HashSet<&i32>>();
        s.remove(&0);
        s.len() as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Count Unique Non-Zero Elements	Time Complexity: O(n). Space Complexity: O(n) due to Python set holding unique numbers.
Approach 2: Sort and Count Changes	Time Complexity: O(n log n). Space Complexity: O(1).
Hash Table or Array	–

Complexity analysis

Approach	Time	Space	When to Use
Count Unique Non-Zero Elements	O(n)	O(n)	Best general solution; fast linear scan using a hash set
Sort and Count Changes	O(n log n)	O(1) extra (in-place sort)	Useful when sorting is already required or avoiding extra hash memory

Frequently asked questions

Is Make Array Zero by Subtracting Equal Amounts easy or hard?

The problem is classified as Easy on LeetCode with an acceptance rate around 70%+. The main challenge is recognizing that each distinct positive number corresponds to one operation, which turns the problem into a simple counting task.

Make Array Zero by Subtracting Equal Amounts Python/Java solution

In Python, insert all positive numbers into a set and return its length. In Java, use a HashSet<Integer> and add each non-zero element while iterating through the array. Both implementations run in O(n) time with O(n) extra space.

How to solve Make Array Zero by Subtracting Equal Amounts in O(n)?

Traverse the array and add every positive element to a hash set. Because each distinct value corresponds to one subtraction operation, the final answer is simply the number of unique non-zero values. This avoids simulating the subtraction process and achieves O(n) time complexity.

What is the best approach for Make Array Zero by Subtracting Equal Amounts?

The best approach is counting the number of distinct non-zero elements in the array. Each unique positive value represents one subtraction round where the smallest remaining value is removed from all positive numbers. Using a hash set allows this to be computed in O(n) time with O(n) space.

Is Make Array Zero by Subtracting Equal Amounts asked at Google/Amazon/Meta?

Problems with similar greedy insights and array processing patterns commonly appear in interviews at companies like Amazon and Google. While this exact problem may not always appear, understanding how to reduce repeated operations into counting distinct values is a useful interview pattern.

What data structure is used in Make Array Zero by Subtracting Equal Amounts?

The optimal solution uses a hash set to track distinct non-zero values in the array. This allows constant-time insertion and ensures each value is counted once. The alternative solution relies on sorting the array and scanning for value transitions.

What is the time complexity of Make Array Zero by Subtracting Equal Amounts?

The optimal solution runs in O(n) time by scanning the array once and inserting non-zero elements into a hash set. The alternative sorting approach runs in O(n log n) time due to the sorting step, followed by a linear scan.

Make Array Zero by Subtracting Equal Amounts solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Count Unique Non-Zero Elements

Approach 2: Approach 2: Sort and Count Changes

Approach 3: Hash Table or Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Make Array Zero by Subtracting Equal Amounts solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Count Unique Non-Zero Elements

Approach 2: Approach 2: Sort and Count Changes

Approach 3: Hash Table or Array

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems