# 2826. Sorting Three Groups

## Problem Statement

<br>

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:

1. Sort the numbers in each group independently.
2. Append the elements of groups `1`, `2`, and `3` to `res` **in 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***.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [2,1,3,2,1]
</strong><strong>Output: 3
</strong><strong>Explanation: It's optimal to perform three operations:
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,3,2,1,3,3]
</strong><strong>Output: 2
</strong><strong>Explanation: It's optimal to perform two operations:
</strong>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.
</code></pre>

**Example 3:**

<pre><code><strong>Input: nums = [2,2,2,2,3,3]
</strong><strong>Output: 0
</strong><strong>Explanation: It's optimal to not perform operations.
</strong>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.
</code></pre>

&#x20;

**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

<https://leetcode.com/problems/sorting-three-groups/description/>

### 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
```

{% code title="C++" lineNumbers="true" %}

```cpp
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
    */
};
```

{% endcode %}

### Approach 2:

```
LIS
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    int minimumOperations(vector<int>& arr) {
        int n = arr.size();
        vector<int> dp(n,1);
        int maxi = 1;

        for(int index=1; index<n; index++){
            for(int prev=0; prev<index; prev++){
                if(arr[prev] <= arr[index]){
                    if(1 + dp[prev] > dp[index]){
                        dp[index] = 1 + dp[prev];
                        maxi = max(maxi, dp[index]);
                    }
                }
            }
        }

        return n-maxi;
    }
};
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###