Minimum Operations to Convert All Elements to Zero
MedPrompt
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.
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We handle the numbers in increasing order of their value. For each value v, we determine how many operations are needed to clear all of its occurrences. An operation to clear v requires selecting a subarray where v is the minimum non-negative integer. This is only possible if the subarray contains no zeros. As we process values in increasing order (1, 2, 3, ...), when we are at value v, all numbers smaller than v have already been turned to zero. Therefore, the zeros in the array act as separators. Occurrences of v that are in different contiguous blocks of non-zero numbers cannot be cleared by a single operation. Thus, for each value v, the number of operations required is equal to the number of distinct non-zero blocks that contain at least one v.
Algorithm
- Create a copy of the input array,
current_nums, to modify during the simulation. - Find all unique non-zero values in the array and sort them in ascending order.
- Initialize
total_operations = 0. - Iterate through each unique value
vfrom smallest to largest:- Scan
current_numsto identify contiguous blocks of non-zero elements. - For each non-zero block, check if it contains the value
v. - The number of operations for
vis the count of such blocks. - Add this count to
total_operations. - After processing
v, updatecurrent_numsby setting all occurrences ofvto 0. This simulates the clearance ofvand prepares the array for the next value.
- Scan
- Return
total_operations.
Walkthrough
The simulation proceeds value by value. We start with the smallest non-zero number and count the operations needed for it, then move to the next smallest, and so on. To count operations for a value v, we look at the current state of the array (where all numbers < v are zero). We identify contiguous segments of non-zero numbers. Each such segment that contains v requires one operation. After counting, we set all v's to zero to simulate their removal before processing the next value.
import java.util.*; class Solution { public int minOperations(int[] nums) { int n = nums.length; int[] currentNums = Arrays.copyOf(nums, n); Set<Integer> uniqueValsSet = new HashSet<>(); for (int num : currentNums) { if (num > 0) { uniqueValsSet.add(num); } } List<Integer> sortedUniqueVals = new ArrayList<>(uniqueValsSet); Collections.sort(sortedUniqueVals); int totalOperations = 0; for (int val : sortedUniqueVals) { int opsForVal = 0; boolean inBlock = false; boolean blockContainsVal = false; for (int i = 0; i < n; i++) { if (currentNums[i] > 0) { if (!inBlock) { inBlock = true; blockContainsVal = false; } if (currentNums[i] == val) { blockContainsVal = true; } } else { // currentNums[i] == 0 if (inBlock) { if (blockContainsVal) { opsForVal++; } inBlock = false; } } } // Check for the last block if (inBlock && blockContainsVal) { opsForVal++; } totalOperations += opsForVal; // Set all occurrences of val to 0 for the next iteration for (int i = 0; i < n; i++) { if (currentNums[i] == val) { currentNums[i] = 0; } } } return totalOperations; }}Complexity
Time
O(U * N), where N is the number of elements and U is the number of unique non-zero values in the array. In the worst case, U can be up to N, leading to an O(N^2) complexity. The outer loop runs U times, and inside it, we iterate through the array of size N multiple times.
Space
O(N), where N is the number of elements in the array. This is for storing the copy of the array and the set of unique values.
Trade-offs
Pros
The logic is straightforward and closely follows the problem's state changes.
It's relatively easy to implement.
Cons
The time complexity is high, making it unsuitable for large inputs as it will likely result in a 'Time Limit Exceeded' error.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.