3542. Minimum Operations to Convert All Elements to Zero

[mah-shamim]

Topics: Array, Hash Table, Stack, Greedy, Monotonic Stack, Biweekly Contest 156

You are given an array nums of size n, consisting of non-negative integers.
Your task is to apply some (possibly zero) operations on the array so that all elements become 0.

In one operation, you can select a subarray¹ [i, j] (where 0 <= i <= j < n) and set all occurrences of the minimum non-negative integer in that subarray to 0.

Return the minimum number of operations required to make all elements in the array 0.

Example 1:

• Input: nums = [0,2]
• Output: 1
• Explanation:
  • Select the subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].
  • Thus, the minimum number of operations required is 1.

Example 2:

• Input: nums = [3,1,2,1]
• Output: 3
• Explanation:
  • Select subarray [1,3] (which is [1,2,1]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [3,0,2,0].
  • Select subarray [2,2] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [3,0,0,0].
  • Select subarray [0,0] (which is [3]), where the minimum non-negative integer is 3. Setting all occurrences of 3 to 0 results in [0,0,0,0].
  • Thus, the minimum number of operations required is 3.

Example 3:

• Input: nums = [1,2,1,2,1,2]
• Output: 4
• Explanation:
  • Select subarray [0,5] (which is [1,2,1,2,1,2]), where the minimum non-negative integer is 1. Setting all occurrences of 1 to 0 results in [0,2,0,2,0,2].
  • Select subarray [1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,2,0,2].
  • Select subarray [3,3] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,2].
  • Select subarray [5,5] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0,0,0,0,0].
  • Thus, the minimum number of operations required is 4.

Example 4:

• Input: nums = [7,2,0,4,2]
• Output: 4

Constraints:

• 1 <= n == nums.length <= 10⁵
• 0 <= nums[i] <= 10⁵

Hint:

1. Process the values in nums from smallest to largest (excluding 0).
2. For each target value v, identify its maximal contiguous segments (subarrays where nums[i] == v); each segment can be zeroed out in one operation.
3. After setting those segments to zero, dynamically update the remaining array and repeat with the next value.

Footnotes

1. Subarray: A subarray is a contiguous sequence of elements within an array. ↩

[mah-shamim]

We want to find the minimum number of operations to make all elements in the array nums equal to zero.
The key observation is that we only need to count the number of increasing “steps” in the array when we move from left to right.

Approach:

• In each operation, we can select a subarray and make the minimum non-zero element in it zero.
• So, every time the array increases to a new positive height, we need a new operation to handle that value later.
• When the array decreases or remains the same, we don’t need to increment the operation count, because smaller values (or zeros) can be handled in the same or earlier operations.

Thus, we can use a monotonic stack to track the increasing sequence of numbers:

• Keep popping from the stack while the top of the stack is greater than the current number — this means we’ve returned to a lower or equal height.
• If the current number is greater than the last number in the stack, it indicates a new “step up,” requiring a new operation.
• Push this number to the stack.
• The final count of such “step-ups” gives the minimum number of operations.

Let's implement this solution in PHP: 3542. Minimum Operations to Convert All Elements to Zero

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function minOperations($nums) {
    $ans = 0;
    $stack = [];
    array_push($stack, 0);

    foreach ($nums as $num) {
        while (!empty($stack) && end($stack) > $num) {
            array_pop($stack);
        }
        if (empty($stack) || end($stack) < $num) {
            $ans++;
            array_push($stack, $num);
        }
    }

    return $ans;
}

// Test cases
$nums1 = [0, 2];
$nums2 = [3, 1, 2, 1];
$nums3 = [1, 2, 1, 2, 1, 2];
$nums4 = [7,2,0,4,2];

echo minOperations($nums1) . "\n"; // Output: 1
echo minOperations($nums2) . "\n"; // Output: 3
echo minOperations($nums3) . "\n"; // Output: 4
echo minOperations($nums4) . "\n"; // Output: 4
?>

Explanation:

1. Pop larger elements:

   • While the top of the stack is greater than the current number, we remove it.
   • This means we’ve gone down to a smaller or equal value, so higher values are no longer relevant.

2. Count new increases:

   • If the current number is greater than the top of the stack, it indicates a new “increase” or a new unique positive value that will eventually need to be zeroed out in its own operation.
   • Therefore, we increment the operation count and push the current number onto the stack.

Time and Space Complexity

• Time Complexity: O(n)

  • Each element is pushed and popped at most once from the stack.

• Space Complexity: O(n)

  • In the worst case (strictly increasing array), the stack may hold all elements.

[kovatz]

Thanks for solving the problem of "Minimum Operations to Convert All Elements to Zero"

[mah-shamim]

Thanks