easy Make Array Zero by Subtracting Equal Amounts

Problem Statement

Given an array of positive integers nums, return the minimum number of operations required to make all elements of nums 0.

In one operation, you must:

Select a positive integer n such that n is less than or equal to the smallest positive element in nums.
Subtract n from every non-zero element in nums.

Examples

Example 1:
- Input: nums = [3,3,2]
- Expected Output: 2
- Justification: Subtract 2 from all non-zero elements to get [1,1,0]. Then, subtract 1 to get all zeros. 2 steps are required.
Example 2:
- Input: [1,2,3,4,5]
- Expected Output: 5
- Justification: Since all elements are unique, each step involves subtracting 1 from a unique non-zero element, requiring 5 steps to turn the array into zeros.
Example 3:
- Input: [4,4,4,3,3,2,2,1]
- Expected Output: 4
- Justification: After removing duplicates, we have [4,3,2,1]. Each number represents a unique subtraction step, hence 4 steps are needed.

Try it yourself

Try solving this question here:

✅ Solution Make Array Zero by Subtracting Equal Amounts

Problem Statement

Given an array of positive integers nums, return the minimum number of operations required to make all elements of nums 0.

In one operation, you must:

Select a positive integer n such that n is less than or equal to the smallest positive element in nums.
Subtract n from every non-zero element in nums.

Examples

Example 1:
- Input: nums = [3,3,2]
- Expected Output: 2
- Justification: Subtract 2 from all non-zero elements to get [1,1,0]. Then, subtract 1 to get all zeros. 2 steps are required.
Example 2:
- Input: [1,2,3,4,5]
- Expected Output: 5
- Justification: Since all elements are unique, each step involves subtracting 1 from a unique non-zero element, requiring 5 steps to turn the array into zeros.
Example 3:
- Input: [4,4,4,3,3,2,2,1]
- Expected Output: 4
- Justification: After removing duplicates, we have [4,3,2,1]. Each number represents a unique subtraction step, hence 4 steps are needed.

Solution

To solve this problem, the most effective strategy is to focus on the unique non-zero elements in the array. Since subtracting the same amount from different numbers doesn't depend on the numbers being consecutive or related, we can essentially "ignore" the operation's effect on the array's structure and simply count how many unique operations we can perform. This approach is efficient because it directly correlates the number of steps to the number of unique non-zero values in the array, bypassing the need to simulate each subtraction operation.

First, we filter out all zeros from the array since they do not affect the operation count. Then, by converting the remaining numbers to a set, we eliminate duplicates, leaving us with the unique non-zero values. The size of this set directly gives us the answer: it represents the minimum number of distinct subtraction operations needed to reduce every element to zero. This method is straightforward and avoids unnecessary computations, making it an optimal solution for the problem.

Step-by-step Algorithm

Initialize a Set: Start by creating an empty set. This set will be used to store the unique non-zero elements found in the input array. The use of a set ensures that each element is counted only once, regardless of how many times it appears in the array.
Iterate Over the Array: Loop through each element in the input array. For each element, check if it is greater than zero. We are only interested in non-zero elements because zeros do not affect our operation count.
Add Non-Zero Elements to the Set: If an element is greater than zero, add it to the set created in step 1. Since sets automatically handle duplicates, any repeated non-zero value will not affect the size of the set.
Calculate the Size of the Set: After all non-zero elements have been added to the set, the size of the set represents the number of unique non-zero values in the original array. This size directly corresponds to the minimum number of steps required to reduce all elements to zero.
Return the Size of the Set: The final step of the algorithm is to return the size of the set as the answer. This value indicates the minimum number of subtraction operations needed to turn the array into all zeros.

Algorithm Walkthrough

Given the input [4,4,4,3,3,2,2,1], let's walk through the algorithm:

Initialize a Set: Create an empty set to store unique non-zero values.
Iterate Over the Array:
- First element, 4: It's greater than zero, so add it to the set.
- Second element, 4: Already exists in the set, so it's ignored.
- Third element, 4: Same as above, ignored.
- Fourth element, 3: It's greater than zero and not in the set, so add it.
- Fifth element, 3: Already exists in the set, so it's ignored.
- Sixth element, 2: It's greater than zero and not in the set, so add it.
- Seventh element, 2: Already exists in the set, so it's ignored.
- Eighth element, 1: It's greater than zero and not in the set, so add it.
Add Non-Zero Elements to the Set: After iterating through the array, the set contains the elements {1, 2, 3, 4}.
Calculate the Size of the Set: The set size is 4, representing the four unique non-zero values in the array.
Return the Size of the Set: Return 4 as the minimum number of steps required to reduce the array to zeros.

Code

java

import java.util.HashSet;
import java.util.Set;

public class Solution {

  public int minOperations(int[] nums) {
    Set<Integer> uniqueNumbers = new HashSet<>(); // Step 1: Initialize a Set

    for (int num : nums) { // Step 2: Iterate Over the Array
      if (num > 0) { // Check if element is greater than zero
        uniqueNumbers.add(num); // Step 3: Add Non-Zero Elements to the Set
      }
    }

    // Step 4 & 5: Calculate the Size of the Set and Return it
    return uniqueNumbers.size();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test the function with the example inputs
    System.out.println(solution.minOperations(new int[] { 3, 3, 2 })); // Example 1
    System.out.println(solution.minOperations(new int[] { 1, 2, 3, 4, 5 })); // Example 2
    System.out.println(
      solution.minOperations(new int[] { 4, 4, 4, 3, 3, 2, 2, 1 })
    ); // Example 3
  }
}

Complexity Analysis

Time Complexity

The primary operation in the algorithm is iterating through the input array once, leading to an overall time complexity, where N is the number of elements in the array.

Space Complexity

The extra space is used to store unique non-zero elements in a set or map. In the worst case, if all elements are unique and non-zero, the space complexity would be . However, since we're focusing on the unique non-zero elements, it's more precise to denote it as .

🤖 Don't fully get this? Learn it with Claude

Stuck on Make Array Zero by Subtracting Equal Amounts? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Make Array Zero by Subtracting Equal Amounts** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Make Array Zero by Subtracting Equal Amounts** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Make Array Zero by Subtracting Equal Amounts**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Make Array Zero by Subtracting Equal Amounts**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Can Place Flowers Set Mismatch →