You are given a 0-indexed integer array nums of length n.
The numbers from 0 to n - 1 are divided into three groups numbered from 1 to 3, where number i belongs to group nums[i]. Notice that some groups may be empty.
You are allowed to perform this operation any number of times:
Pick number x and change its group. More formally, change nums[x] to any number from 1 to 3.
A new array res is constructed using the following procedure:
Sort the numbers in each group independently.
Append the elements of groups 1, 2, and 3 to resin this order.
Array nums is called a beautiful array if the constructed array res is sorted in non-decreasing order.
Return the minimum number of operations to make nums a beautiful array.
Example 1:
Input: nums = [2,1,3,2,1]
Output: 3
Explanation: It's optimal to perform three operations:
1. change nums[0] to 1.
2. change nums[2] to 1.
3. change nums[3] to 1.
After performing the operations and sorting the numbers in each group, group 1 becomes equal to [0,1,2,3,4] and group 2 and group 3 become empty. Hence, res is equal to [0,1,2,3,4] which is sorted in non-decreasing order.
It can be proven that there is no valid sequence of less than three operations.
Example 2:
Input: nums = [1,3,2,1,3,3]
Output: 2
Explanation: It's optimal to perform two operations:
1. change nums[1] to 1.
2. change nums[2] to 1.
After performing the operations and sorting the numbers in each group, group 1 becomes equal to [0,1,2,3], group 2 becomes empty, and group 3 becomes equal to [4,5]. Hence, res is equal to [0,1,2,3,4,5] which is sorted in non-decreasing order.
It can be proven that there is no valid sequence of less than two operations.
Example 3:
Input: nums = [2,2,2,2,3,3]
Output: 0
Explanation: It's optimal to not perform operations.
After sorting the numbers in each group, group 1 becomes empty, group 2 becomes equal to [0,1,2,3] and group 3 becomes equal to [4,5]. Hence, res is equal to [0,1,2,3,4,5] which is sorted in non-decreasing order.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 3
Intuition
Bascially
[2,2,3,1,2,2]
When travering keep a target to compare prev
Let say at index 2
we have two choices make 3 to 3 or 2
To maintain the order
and if less than target update operation count appropriately
Approach 2:
Find the maximum LIS and subtract with the max length
See for yourself
Links
Video Links
Approach 1:
Recursion
For loop from 1 to 3
to check for 1st index as target
Earlier we were mentioning directly arr[0] as target
C++
class Solution {
public:
int find_ans(vector<int>& arr, int index, int target, int n){
if(index == n)
return 0;
int ops;
if(arr[index] == target)
ops = find_ans(arr, index+1, target, n);
else if(arr[index] > target)
ops = min( find_ans(arr, index+1, target, n)+1, find_ans(arr, index+1, arr[index], n));
else
ops = find_ans(arr, index+1, target, n) + 1;
return ops;
}
int minimumOperations(vector<int>& arr) {
int n = arr.size();
int index = 1;
int mini = INT_MAX;
for(int i=1; i<=3; i++){
if(arr[0] == i)
mini = min(mini, find_ans(arr, index, i, n));
else
mini = min(mini, find_ans(arr, index, i, n) + 1 );
}
return mini;
}
/*
[3,1,2]
1
*/
};