LeetCode Problem 2357

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue), Simulation

Solution

LeetCode 2357 - Make Array Zero by Subtracting Equal Amounts

Problem Understanding

This problem gives us an array nums containing non-negative integers. We want to transform the entire array into zeros using a specific operation.

In a single operation, we must choose a positive integer x that is less than or equal to the smallest non-zero value currently present in the array. After choosing x, we subtract it from every positive element in the array. Elements that are already zero remain unchanged.

Our goal is to determine the minimum number of operations required to make every element equal to zero.

A key detail is that the chosen value x must not exceed the smallest non-zero element. Since all positive elements are reduced by the same amount, the smallest non-zero element will always become zero after an operation if we choose x equal to that smallest value.

The constraints are quite small:

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

This means even relatively inefficient approaches would work. However, the problem contains an important observation that leads to a very simple optimal solution.

Important Edge Cases

If the array contains only zeros, no operations are needed and the answer is 0.

If the array contains only one positive value, exactly one operation is required.

Duplicate values are important because multiple occurrences of the same positive number can be eliminated together.

Arrays with a mix of zeros and positive numbers should ignore zeros when counting required operations.

Approaches

Brute Force

A direct simulation follows the operation exactly as described.

At each step:

1. Find the smallest non-zero element.
2. Use that value as x.
3. Subtract it from every positive element.
4. Count the operation.
5. Repeat until all elements become zero.

This works because choosing the smallest non-zero value is always optimal. Any smaller value would require additional operations later.

The approach is correct because it literally performs the process described in the problem statement. However, it repeatedly scans the array to find the smallest non-zero value and then scans again to perform the subtraction.

Key Insight

Instead of simulating the process, consider what actually happens.

Suppose the positive values are:

1, 3, 5

After subtracting 1, the values become:

0, 2, 4

After subtracting 2, they become:

0, 0, 2

After subtracting 2 again, everything becomes zero.

Notice that each operation eliminates exactly one distinct positive value level.

More generally:

• Every unique positive number eventually becomes the smallest non-zero value once.
• When it becomes the smallest non-zero value, one operation eliminates that level completely.
• Duplicate values disappear together in the same operation.

Therefore, the answer is simply the number of distinct positive integers in the array.

For example:

[1,5,0,3,5]

Distinct positive values:

{1,3,5}

Count = 3

Answer = 3.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(1)	Simulates every operation, where k is the number of operations
Optimal	O(n)	O(n)	Count distinct positive values using a set

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty hash set.
2. Iterate through every number in nums.
3. If the current number is greater than zero, insert it into the set.
4. Ignore all zeros because they already require no work.
5. After processing the entire array, return the size of the set.

The hash set automatically removes duplicates, so each distinct positive value is counted exactly once.

Why it works

Each operation removes the current smallest positive value from the array. Distinct positive values disappear one level at a time. If there are k unique positive numbers, exactly k operations are needed because each operation can eliminate only one distinct positive level. Conversely, choosing the smallest positive value always eliminates one level completely, so k operations are sufficient. Therefore, the answer equals the number of distinct positive integers.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        distinct_positive = set()

        for num in nums:
            if num > 0:
                distinct_positive.add(num)

        return len(distinct_positive)

The implementation creates a set called distinct_positive.

As we iterate through the array, every positive number is inserted into the set. Since sets automatically store unique values, duplicate numbers are counted only once.

Zeros are ignored because they already satisfy the target state and never contribute to additional operations.

Finally, the size of the set is returned, which equals the number of distinct positive values and therefore the minimum number of operations.

Go Solution

func minimumOperations(nums []int) int {
	distinctPositive := make(map[int]struct{})

	for _, num := range nums {
		if num > 0 {
			distinctPositive[num] = struct{}{}
		}
	}

	return len(distinctPositive)
}

The Go solution uses a map as a hash set because Go does not provide a built-in set type.

The map keys store the distinct positive numbers, while the empty struct value consumes essentially no extra storage.

The logic is otherwise identical to the Python implementation. There are no concerns about integer overflow because all values are at most 100.

Worked Examples

Example 1

Input:

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

Processing:

Element	Positive?	Set After Processing
1	Yes	{1}
5	Yes	{1, 5}
0	No	{1, 5}
3	Yes	{1, 3, 5}
5	Yes	{1, 3, 5}

Final set:

{1,3,5}

Size:

3

Answer:

3

Example 2

Input:

nums = [0]

Processing:

Element	Positive?	Set After Processing
0	No	{}

Final set:

{}

Size:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(n)	In the worst case every positive value is distinct

The algorithm performs a single pass through the array. Each set insertion is an average-case O(1) operation, giving overall linear time complexity.

The set may contain every element if all positive values are distinct, resulting in O(n) auxiliary space.

Test Cases

sol = Solution()

assert sol.minimumOperations([1, 5, 0, 3, 5]) == 3  # provided example
assert sol.minimumOperations([0]) == 0  # all zeros
assert sol.minimumOperations([1]) == 1  # single positive value
assert sol.minimumOperations([5, 5, 5]) == 1  # duplicates only
assert sol.minimumOperations([1, 2, 3, 4]) == 4  # all distinct positives
assert sol.minimumOperations([0, 0, 0, 0]) == 0  # multiple zeros
assert sol.minimumOperations([0, 1, 0, 1, 0]) == 1  # zeros mixed with duplicates
assert sol.minimumOperations([2, 2, 3, 3, 4, 4]) == 3  # several duplicate groups
assert sol.minimumOperations([100]) == 1  # maximum value
assert sol.minimumOperations([0, 100, 99, 100, 99, 98]) == 3  # large distinct values

Test Summary

Test	Why
[1,5,0,3,5]	Official example with duplicates and zeros
[0]	Smallest all-zero input
[1]	Single positive value
[5,5,5]	All values identical
[1,2,3,4]	Every positive value distinct
[0,0,0,0]	Multiple zeros only
[0,1,0,1,0]	Zeros mixed with duplicates
[2,2,3,3,4,4]	Multiple duplicate groups
[100]	Maximum allowed value
[0,100,99,100,99,98]	Larger values with duplicates

Edge Cases

Array Contains Only Zeros

An input such as:

[0,0,0]

already satisfies the goal. A buggy implementation might incorrectly count zero as a distinct value. The solution explicitly ignores zeros, producing an empty set and returning 0.

All Positive Values Are Equal

Consider:

[7,7,7,7]

Although there are four elements, they all disappear in a single operation by choosing x = 7. The set contains only one distinct positive value, so the algorithm correctly returns 1.

Every Positive Value Is Different

Consider:

[1,2,3,4,5]

Each distinct level must eventually be eliminated separately. The set contains five values, so the answer is 5. This validates that the algorithm counts distinct positive values rather than total elements.

Zeros Mixed With Positive Numbers

Consider:

[0,0,2,2,5]

Zeros should not affect the answer because they never participate in operations. The implementation ignores zeros entirely and counts only {2,5}, returning 2, which is correct.