#3542

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Operations to Convert All Elements to Zero

Calculate the fewest operations to turn all numbers in an array to zero using subarray minimum elimination strategy.

array hash table stack greedy monotonic stack

Problem Statement

You are given an array nums consisting of non-negative integers. You can perform operations to reduce elements to zero by selecting subarrays and zeroing their minimum non-negative values. The goal is to determine the minimum number of operations needed to make every element zero.

In one operation, you may choose any subarray [i, j] (0 <= i <= j < n) and set all instances of the current minimum value within that subarray to zero. Return the smallest number of operations required to fully convert the array into zeros.

Examples

Example 1

Input: nums = [0,2]

Output: 1

Example 2

Input: nums = [3,1,2,1]

Output: 3

Example 3

Input: nums = [1,2,1,2,1,2]

Output: 4

Constraints

1 <= n == nums.length <= 105
0 <= nums[i] <= 105

Solution Approach

Sort and Map Values

Identify all unique non-zero numbers and store their indices in a hash map. This allows efficient tracking of where each value occurs and avoids repeated scans.

Process from Smallest to Largest

Iterate over the values starting from the smallest non-zero element. For each, scan its positions and apply subarray operations, ensuring you cover contiguous blocks efficiently. This prevents redundant operations on already zeroed elements.

Use Stack or Greedy Scanning

Maintain a stack to track subarray boundaries while applying operations. This pattern ensures that overlapping ranges are handled with minimal moves, leveraging the monotonic stack principle for array scanning plus hash lookup optimization.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on iterating through unique values and processing their positions, roughly O(n log n) for sorting plus O(n) scanning. Space complexity is O(n) for storing index mappings in a hash table.

What Interviewers Usually Probe

Focus on efficiently finding the minimum in subarrays without repeated full scans.
Consider hash maps to quickly locate element positions instead of naive iteration.
Stack or monotonic scanning patterns hint at reducing overlapping operation counts.

Common Pitfalls or Variants

Common pitfalls

Failing to process elements in ascending order can increase operation count unnecessarily.
Neglecting contiguous blocks leads to redundant subarray operations.
Using repeated full scans instead of index maps causes timeouts for large arrays.

Follow-up variants

Change operation to set maximum instead of minimum, requiring reverse processing.
Limit subarray length, forcing more careful selection and increased operations.
Allow decrement by one instead of full zeroing, increasing scan complexity.

FAQ

What is the best way to minimize operations in Minimum Operations to Convert All Elements to Zero?

Process numbers from smallest to largest and use a hash map for indices to efficiently select subarrays that zero out multiple elements in one operation.

Does using a stack improve the solution?

Yes, maintaining subarray boundaries with a stack helps prevent redundant operations on overlapping sections and leverages the monotonic scan pattern.

Can we skip zero elements during processing?

Absolutely. Ignoring zeros prevents unnecessary subarray operations and keeps the operation count minimal.

What is the typical time complexity for this problem?

Sorting unique values takes O(n log n), scanning positions is O(n), so overall it's roughly O(n log n) with extra O(n) space for hash mapping.

Is this problem mainly an Array scanning plus hash lookup pattern?

Yes, the key pattern is array scanning combined with hash-based position tracking to efficiently select subarrays for zeroing.

terminal

Solution

Solution 1: Monotonic Stack

According to the problem description, we should first convert the smallest numbers to $0$, then the second smallest numbers to $0$, and so on. During this process, if two numbers are separated by smaller numbers, they require an additional operation to become $0$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        stk = []
        ans = 0
        for x in nums:
            while stk and stk[-1] > x:
                ans += 1
                stk.pop()
            if x and (not stk or stk[-1] != x):
                stk.append(x)
        ans += len(stk)
        return ans

Continue Practicing

#3523 make array non decreasing #3229 minimum operations to make array equal to target #2818 apply operations to maximize score