Minimum Operations To Convert All Elements To Zero
01 · Problem
You are given an array nums of non-negative integers. In one operation you choose any non-empty subarray nums[i..j], find the minimum value m inside that subarray, and set every element of the subarray equal to m to 0. Elements outside the subarray, and elements of the subarray that are larger than m, are left unchanged.
Return the minimum number of operations required to make every element of nums equal to 0. If the array is already all zeros the answer is 0.
02 · Examples
nums = [0,2]
1
Choose the subarray [2] (indices 1..1); its minimum is 2, which becomes 0. One operation.
nums = [2,4,1,4,2]
5
One whole-array operation zeroes the 1, giving [2,4,0,4,2]. The zero now splits the array, so each 4 and each 2 on either side needs its own operation: 1 + 2 + 2 = 5.
nums = [5,5,3,5]
3
Zero both leading 5s with the subarray [5,5], zero the 3 on its own, then zero the last 5: 3 operations.
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] <= 105
- 03An array that is already all zeros needs 0 operations
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.