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:
[1,1] (which is [2]), where the minimum non-negative integer is 2. Setting all occurrences of 2 to 0 results in [0,0].Example 2:
Input: nums = [3,1,2,1]
Output: 3
Explanation:
[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].[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].[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].Example 3:
Input: nums = [1,2,1,2,1,2]
Output: 4
Explanation:
[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].[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].[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].[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].
Constraints:
1 <= n == nums.length <= 1050 <= nums[i] <= 105class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
return op(nums, n, 0, n - 1);
}
private int op(int[] nums, int n, int lt, int rt) {
// System.out.println(Arrays.toString(nums));
if (lt > rt)
return 0;
else if (lt == rt) {
if (nums[lt] == 0)
return 0;
nums[lt] = 0;
return 1;
}
int minm = Integer.MAX_VALUE, prev = -1, ops = 1;
for (int i = lt; i <= rt; i++){
if(nums[i]==0){
ops += op(nums, n, prev+1, i-1);
prev = i;
continue;
}
minm = Math.min(minm, nums[i]);
}
for (int i = lt; i <= rt; i++)
if (nums[i] == minm) {
nums[i] = 0;
ops += op(nums, n, prev + 1, i - 1);
prev = i;
}
ops += op(nums, n, prev + 1, n - 1);
return ops;
}
}