2357. Make Array Zero by Subtracting Equal Amounts

EasyGreedyArrayHash TableSortingSimulationHeap (Priority Queue)

Problem Description

In this problem, we are given an array nums containing non-negative integers. Our task is to perform a series of operations to make all elements in the array equal to zero. An operation consists of two steps:

Choose a positive integer x that is no greater than the smallest non-zero element in nums.
Subtract this x from every positive element in nums.

The goal is to find the minimum number of such operations required to reduce all elements in the array to zero.

Intuition

To approach this problem, we observe that each operation will reduce all non-zero elements by the same amount: the smallest non-zero number in the array. This implies that each unique non-zero number in the array will eventually need to become the smallest non-zero element through these operations, and be reduced to zero.

Given this, intuitively, if we repeatedly perform the operation on the current smallest non-zero element, we would effectively eliminate that element in the next step (since it will become zero). In the case of duplicate non-zero elements, these can be removed in the same operation. Therefore, the minimum number of operations needed will be equal to the number of unique non-zero values in the array.

The Python solution reflects this intuition by first filtering out all the zeros and then transforming the remaining numbers into a set, which automatically removes duplicates, leaving us with unique non-zero numbers. The length of this resultant set is exactly the number of operations needed since that's the number of unique non-zero elements we will need to reduce to zero, one by one.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation of the solution is quite straightforward, leveraging Python's set data structure and list comprehension.

Here's a step-by-step breakdown of the solution code:

return len({x for x in nums if x}): This line of code encapsulates the entire solution in a compact form.
- {x for x in nums if x} is a set comprehension, which iterates over each element x in the list nums.
- The if x part is a conditional that filters out all zero elements. This is important because the problem specifies that we should only consider positive elements for subtraction operations.
- By using a set rather than a list, duplicate non-zero values are automatically eliminated. This is crucial to finding the unique non-zero values.
len(...): After the set is created with only unique non-zero values, the len function is used to count the number of elements in this set.

No additional algorithms or complex patterns are required for this operation; the solution is primarily based on the properties of sets in Python that give us unique values naturally.

The algorithm's complexity is O(n), where n is the number of elements in the input list nums. This is because the set comprehension iterates over the list once, and set operations are generally O(1) on average. Therefore, the overall computation is very efficient for this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the example array nums with the following integers:

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

To follow the solution approach using the Python code mentioned earlier, we perform the following steps:

The set comprehension {x for x in nums if x} evaluates as follows:
- Begin iterating over each element x in nums.
- Check if x to filter out zeroes, leaving us with just the positive integers [1, 2, 2, 3].
- As these values are being added to a set, the duplicates are removed, resulting in the unique non-zero values: {1, 2, 3}.
Now, we apply the len(...) function on this resulting set {1, 2, 3}.
- The len function counts the number of unique non-zero elements, resulting in 3.

Therefore, the minimum number of operations required to reduce all elements in nums to zero is 3. These operations would be performed as follows:

First operation: Choose x = 1, the smallest positive integer in nums. Subtract 1 from all positive elements to get [0, 1, 0, 1, 2].
Second operation: Now the smallest non-zero element is 1. Subtract 1 again from all positive elements to get [0, 0, 0, 0, 1].
Third operation: Finally, choose x = 1 one last time to subtract from the remaining positive element. The resulting array is [0, 0, 0, 0, 0].

Now all elements in the array are zero, and it took us 3 operations, which is consistent with the length of the set computed earlier.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumOperations(self, nums: List[int]) -> int:
5        # Create a set comprehension to filter out all non-zero unique elements.
6        unique_non_zero_numbers = {number for number in nums if number}
7
8        # The length of this set represents the minimum number of operations needed,
9        # since each unique non-zero number can be reduced to zero in one operation.
10        return len(unique_non_zero_numbers)
11
12# Example usage:
13# sol = Solution()
14# result = sol.minimumOperations([1, 5, 0, 1, 0])
15# print(result)  # Output would be 2 (for the numbers 1 and 5)
16

1class Solution {
2    public int minimumOperations(int[] nums) {
3        // Initialize a boolean array to keep track of visited numbers
4        boolean[] seenNumbers = new boolean[101]; 
5        seenNumbers[0] = true; // Assuming 0 is not considered as an operation
6        int operationCount = 0; // Initialize a counter for the minimum number of operations
7      
8        // Loop through each number in the input array
9        for (int number : nums) {
10            // If the number has not been seen before
11            if (!seenNumbers[number]) {
12                operationCount++; // Increment the operation count
13                seenNumbers[number] = true; // Mark the number as seen
14            }
15        }
16        // Return the count of the minimum number of operations needed
17        return operationCount;
18    }
19}
20

1#include <vector> // Required for std::vector
2
3// Definition of the Solution class
4class Solution {
5public:
6    // Function to find the minimum number of operations needed to make all elements in an array unique
7    int minimumOperations(std::vector<int>& nums) {
8        // Create an array to keep track of numbers we've seen
9        bool seen[101] = {false}; 
10        seen[0] = true; // We start by marking 0 as seen (if we're assuming that nums only contains positive integers, 
11                        // then this is redundant as it would never be used)
12      
13        int operations = 0; // Initialize the count of operations to 0
14
15        // Loop through each number in the input vector
16        for (int& num : nums) {
17            // If we haven't seen this number before
18            if (!seen[num]) {
19                operations++;     // Increment the count of operations
20                seen[num] = true; // Mark the number as seen
21            }
22        }
23
24        // Return the total number of operations required
25        return operations;
26    }
27};
28

1/**
2 * This function calculates the minimum number of operations to make all elements of an array equal.
3 * An operation is defined as incrementing n - 1 elements by 1.
4 * 
5 * @param {number[]} nums - The input array of numbers.
6 * @returns {number} The minimum number of operations to make all elements equal.
7 */
8function minimumOperations(nums: number[]): number {
9    // Initialize a set to store unique non-zero elements
10    const uniqueNonZeroElements = new Set<number>();
11
12    // Iterate through the input array
13    for (let num of nums) {
14        // If the current number is not zero, add it to the set
15        if (num !== 0) {
16            uniqueNonZeroElements.add(num);
17        }
18    }
19
20    // The size of the set gives the minimum number of operations
21    // since we need to make only the unique non-zero elements equal
22    return uniqueNonZeroElements.size;
23}
24

Time and Space Complexity

The given Python code defines a method called minimumOperations that calculates the minimum number of operations needed to make all elements in the array nums equal to zero, under the assumption that in one operation, you can choose any non-zero element and reduce it to zero. This is inferred by the requirement to count unique non-zero elements, as setting each unique non-zero number to zero is effectively the operation implied.

Time Complexity

The time complexity of the code is dominated by the comprehension {x for x in nums if x} which iterates through each element of the nums list once. The membership check for sets in Python is O(1) on average. Therefore, the overall time complexity of creating this set is O(n), where n is the length of the nums list.

Space Complexity

The space complexity is influenced by the additional set that is being created to store the unique non-zero elements. In the worst case, if all elements are unique and non-zero, the set will grow to the same size as the input list. Thus, the space complexity is O(n), where n is the size of the input list. If the input list has many zeros or duplicate elements, the space used will be less than n.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know