> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/2826.-sorting-three-groups.md).

# 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

###


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding-9.gitbook.io/untitled/dynamic-programming/dp-on-lis/2826.-sorting-three-groups.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.