# Sorting Three Groups
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sorting-three-groups)
Canonical: https://scaleengineer.com/dsa/problems/sorting-three-groups
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [UiPath](https://scaleengineer.com/companies/uipath)
---
## Problem
You are given an integer array `nums`. Each element in `nums` is 1, 2 or 3\. In each operation, you can remove an element from `nums`. Return the **minimum** number of operations to make `nums` **non-decreasing**.

**Example 1:**

**Input:** nums = \[2,1,3,2,1\]

**Output:** 3

**Explanation:**

One of the optimal solutions is to remove `nums[0]`, `nums[2]` and `nums[3]`.

**Example 2:**

**Input:** nums = \[1,3,2,1,3,3\]

**Output:** 2

**Explanation:**

One of the optimal solutions is to remove `nums[1]` and `nums[2]`.

**Example 3:**

**Input:** nums = \[2,2,2,2,3,3\]

**Output:** 0

**Explanation:**

`nums` is already non-decreasing.

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 3`

**Follow-up:** Can you come up with an algorithm that runs in `O(n)` time complexity?

# Approaches
## Brute Force by Iterating Split Points
This approach considers all possible ways to partition the array into three segments. The final non-decreasing array will consist of some number of 1s, followed by 2s, then 3s. We can imagine two split points, `i` and `j`, that define these three groups. The first group (indices `0` to `i-1`) contributes 1s, the second (`i` to `j-1`) contributes 2s, and the third (`j` to `n-1`) contributes 3s. We iterate through all possible pairs of `(i, j)` and calculate how many elements we would keep for that partition. The goal is to maximize the number of kept elements.
**Time:** O(n³). The two outer loops for `i` and `j` run `O(n²)` times. Inside, the counting loops take `O(n)` time in total, leading to a cubic time complexity. · **Space:** O(1). We only use a few variables to store counts and loop indices.
**Pros:** Simple to understand and implement.; Correctly explores all possible valid final array structures.
**Cons:** Extremely inefficient with a time complexity of O(n³).; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The core idea is to exhaustively check every possible structure of the final sorted array. A non-decreasing array of `1`s, `2`s, and `3`s must be of the form `[1,...,1, 2,...,2, 3,...,3]`. This structure can be defined by two boundaries: one where the `1`s end and `2`s begin, and another where the `2`s end and `3`s begin. We can represent these boundaries with indices `i` and `j`.

We use two nested loops to iterate through all possible split points `i` and `j`, where `0 <= i <= j <= n`.
For each pair `(i, j)`, we define three segments of the original array: `nums[0...i-1]`, `nums[i...j-1]`, and `nums[j...n-1]`.
We then iterate through these segments to count the number of elements we can keep:
- Count the number of `1`s in the first segment.
- Count the number of `2`s in the second segment.
- Count the number of `3`s in the third segment.

The sum of these counts gives the size of the non-decreasing subsequence for this specific partition. We keep track of the maximum size found across all partitions. Finally, the minimum number of removals is the total number of elements `n` minus the maximum size of the subsequence we found.

```java
class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        int maxKept = 0;

        // i is the split point before which we only keep 1s
        // j is the split point before which we only keep 1s or 2s
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int currentKept = 0;
                // Count 1s in the first part [0, i-1]
                for (int k = 0; k < i; k++) {
                    if (nums[k] == 1) {
                        currentKept++;
                    }
                }
                // Count 2s in the second part [i, j-1]
                for (int k = i; k < j; k++) {
                    if (nums[k] == 2) {
                        currentKept++;
                    }
                }
                // Count 3s in the third part [j, n-1]
                for (int k = j; k < n; k++) {
                    if (nums[k] == 3) {
                        currentKept++;
                    }
                }
                maxKept = Math.max(maxKept, currentKept);
            }
        }
        return n - maxKept;
    }
}
```
### Algorithm
- Initialize `maxKept` to 0 and `n` to the length of `nums`.
- Use a loop to iterate `i` from `0` to `n`. This `i` represents the boundary after which we no longer keep `1`s.
- Inside this loop, use another loop to iterate `j` from `i` to `n`. This `j` represents the boundary after which we no longer keep `2`s.
- For each pair of `(i, j)`, we calculate the number of elements we can keep:
  - Initialize `currentKept` to 0.
  - A third loop iterates from `k = 0` to `i-1` to count the `1`s.
  - A fourth loop iterates from `k = i` to `j-1` to count the `2`s.
  - A fifth loop iterates from `k = j` to `n-1` to count the `3`s.
- Update `maxKept = Math.max(maxKept, currentKept)`.
- After all loops complete, the minimum number of removals is `n - maxKept`.

## Optimized Brute Force with Prefix Sums
This approach is an optimization of the brute force method. The bottleneck in the previous approach was re-calculating the counts of 1s, 2s, and 3s for each partition `(i, j)`. We can pre-calculate the counts of each number up to every index in the array. This is known as a prefix sum (or prefix count) array. With these pre-calculated values, we can find the count of a number within any range `[start, end]` in `O(1)` time, which reduces the overall complexity.
**Time:** O(n²). Pre-computation takes `O(n)`. The nested loops for `i` and `j` run `O(n²)` times, with `O(1)` work inside. · **Space:** O(n). We use three arrays of size `n+1` to store the prefix counts.
**Pros:** Significantly faster than the naive O(n³) brute force approach.; The logic is still based on the intuitive partitioning idea.
**Cons:** Has a quadratic time complexity, which is not optimal.; Uses extra space proportional to the input size.
### Explanation
To improve upon the `O(n³)` brute-force solution, we can optimize the counting step. Instead of recounting elements for every pair of `(i, j)`, we can precompute the counts. We'll use three arrays to store the prefix counts of `1`s, `2`s, and `3`s.

- `prefixOnes[k]` will store the total count of `1`s in `nums[0...k-1]`.
- `prefixTwos[k]` will store the total count of `2`s in `nums[0...k-1]`.
- `prefixThrees[k]` will store the total count of `3`s in `nums[0...k-1]`.

These arrays can be built in a single pass through `nums` in `O(n)` time. After this precomputation, we can find the count of any number in any subarray `nums[start...end]` in `O(1)` time by subtracting prefix counts. For example, the number of `2`s in `nums[i...j-1]` is `prefixTwos[j] - prefixTwos[i]`.

The main logic of iterating through all `(i, j)` pairs remains, but the work inside the loops is now constant time. This brings the total time complexity down from `O(n³)` to `O(n²)`.

```java
class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        int[] prefixOnes = new int[n + 1];
        int[] prefixTwos = new int[n + 1];
        int[] prefixThrees = new int[n + 1];

        for (int i = 0; i < n; i++) {
            prefixOnes[i + 1] = prefixOnes[i] + (nums[i] == 1 ? 1 : 0);
            prefixTwos[i + 1] = prefixTwos[i] + (nums[i] == 2 ? 1 : 0);
            prefixThrees[i + 1] = prefixThrees[i] + (nums[i] == 3 ? 1 : 0);
        }

        int maxKept = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int keptOnes = prefixOnes[i];
                int keptTwos = prefixTwos[j] - prefixTwos[i];
                int keptThrees = prefixThrees[n] - prefixThrees[j];
                maxKept = Math.max(maxKept, keptOnes + keptTwos + keptThrees);
            }
        }
        return n - maxKept;
    }
}
```
### Algorithm
- First, create three prefix count arrays `prefixOnes`, `prefixTwos`, and `prefixThrees`, each of size `n+1`.
- Iterate through `nums` from `i = 0` to `n-1` to populate these arrays. For each index `k`, `prefixOnes[k+1]` will store the count of `1`s in `nums[0...k]`, and similarly for the other numbers.
- Initialize `maxKept` to 0.
- Use two nested loops to iterate through all split points `i` from `0` to `n` and `j` from `i` to `n`.
- Inside the loops, calculate the number of kept elements in O(1) time:
  - `keptOnes = prefixOnes[i]`
  - `keptTwos = prefixTwos[j] - prefixTwos[i]`
  - `keptThrees = prefixThrees[n] - prefixThrees[j]`
- Update `maxKept = Math.max(maxKept, keptOnes + keptTwos + keptThrees)`.
- The final result is `n - maxKept`.

## Dynamic Programming
The most efficient solution uses dynamic programming. The problem is equivalent to finding the longest non-decreasing subsequence of `nums`. Since the elements are only 1, 2, or 3, the structure of this subsequence is simple: a block of 1s, followed by a block of 2s, followed by a block of 3s. We can keep track of the length of the longest non-decreasing subsequence ending in 1, 2, or 3 as we iterate through the array, which allows us to solve the problem in a single pass.
**Time:** O(n). We iterate through the input array only once. · **Space:** O(1). We only use a few constant extra variables to store the DP state.
**Pros:** Optimal solution with linear time complexity.; Extremely efficient in terms of space, using only a constant number of variables.; Satisfies the follow-up question for an O(n) solution.
**Cons:** The logic might be slightly less intuitive to come up with compared to the brute-force approaches.
### Explanation
This approach rephrases the problem from minimizing removals to maximizing the number of elements kept. The elements we keep must form a non-decreasing subsequence. Given the constraints, this subsequence will be composed of zero or more `1`s, followed by zero or more `2`s, followed by zero or more `3`s.

We can find the length of the longest such subsequence using dynamic programming. We maintain three variables representing the state:
- `len1`: The length of the longest non-decreasing subsequence seen so far that consists only of `1`s.
- `len2`: The length of the longest non-decreasing subsequence seen so far that consists of `1`s and `2`s, ending with a `2`.
- `len3`: The length of the longest non-decreasing subsequence seen so far, ending with a `3`.

We iterate through the input array `nums` once. For each element `num`:
- If `num` is 1: It can only extend a sequence of `1`s. So, we increment `len1`.
- If `num` is 2: It can start a new sequence of `2`s after a sequence of `1`s (length `len1 + 1`) or extend an existing sequence of `2`s (length `len2 + 1`). We take the maximum, so `len2 = max(len1, len2) + 1`.
- If `num` is 3: It can follow any of the previous subsequences. We take the maximum length so far (`max(len1, len2, len3)`) and add 1. So, `len3 = max(len1, len2, len3) + 1`.

After iterating through all numbers, the overall longest non-decreasing subsequence length is the maximum of `len1`, `len2`, and `len3`. The minimum removals is `n` minus this length.

```java
class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        // len1: length of LIS ending with 1
        // len2: length of LIS ending with 2
        // len3: length of LIS ending with 3
        int len1 = 0, len2 = 0, len3 = 0;

        for (int num : nums) {
            if (num == 1) {
                len1++;
            } else if (num == 2) {
                len2 = Math.max(len1, len2) + 1;
            } else { // num == 3
                len3 = Math.max(len1, Math.max(len2, len3)) + 1;
            }
        }
        
        // The length of the longest non-decreasing subsequence is the max of the lengths of subsequences ending in 1, 2, or 3.
        // Note that a sequence of only 1s is a valid non-decreasing subsequence.
        int maxLen = Math.max(len1, Math.max(len2, len3));
        return n - maxLen;
    }
}
```
### Algorithm
- Initialize three counters: `len1`, `len2`, `len3` to 0. These will track the length of the longest non-decreasing subsequence ending in 1, 2, and 3, respectively.
- Iterate through each `num` in the input array `nums`.
- Inside the loop, update the counters based on the value of `num`:
  - If `num == 1`: We can extend a sequence of 1s. Increment `len1`.
  - If `num == 2`: A 2 can follow a 1 or another 2. To get the longest sequence, we take `max(len1, len2)` and add 1. Update `len2` with this value.
  - If `num == 3`: A 3 can follow a 1, 2, or 3. We take `max(len1, len2, len3)` and add 1. Update `len3` with this value.
- After the loop, the length of the longest non-decreasing subsequence is `max(len1, len2, len3)`.
- The minimum number of operations is `n - max(len1, len2, len3)`.

# Solutions
### Java

```java
class Solution {
public
  int minimumOperations(List<Integer> nums) {
    int[] f = new int[3];
    for (int x : nums) {
      int[] g = new int[3];
      if (x == 1) {
        g[0] = f[0];
        g[1] = Math.min(f[0], f[1]) + 1;
        g[2] = Math.min(f[0], Math.min(f[1], f[2])) + 1;
      } else if (x == 2) {
        g[0] = f[0] + 1;
        g[1] = Math.min(f[0], f[1]);
        g[2] = Math.min(f[0], Math.min(f[1], f[2])) + 1;
      } else {
        g[0] = f[0] + 1;
        g[1] = Math.min(f[0], f[1]) + 1;
        g[2] = Math.min(f[0], Math.min(f[1], f[2]));
      }
      f = g;
    }
    return Math.min(f[0], Math.min(f[1], f[2]));
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperations(vector<int> &nums) {
    vector<int> f(3);
    for (int x : nums) {
      vector<int> g(3);
      if (x == 1) {
        g[0] = f[0];
        g[1] = min(f[0], f[1]) + 1;
        g[2] = min({f[0], f[1], f[2]}) + 1;
      } else if (x == 2) {
        g[0] = f[0] + 1;
        g[1] = min(f[0], f[1]);
        g[2] = min(f[0], min(f[1], f[2])) + 1;
      } else {
        g[0] = f[0] + 1;
        g[1] = min(f[0], f[1]) + 1;
        g[2] = min(f[0], min(f[1], f[2]));
      }
      f = move(g);
    }
    return min({f[0], f[1], f[2]});
  }
};

```

### Python

```python
class Solution:
    def minimumOperations(self, nums: List[int]) -> int: f = g = h = 0 for x in nums: ff = gg = hh = 0 if x == 1: ff = f gg = min(f, g) + 1 hh = min(f, g, h) + 1 elif x == 2: ff = f + 1 gg = min(f, g) hh = min(f, g, h) + 1 else: ff = f + 1 gg = min(f, g) + 1 hh = min(f, g, h) f, g, h = ff, gg, hh return min(f, g, h)

```