2826. Sorting Three Groups

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.

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int res = INT_MAX, n = nums.size();
        vector<vector<int>> pre(4,vector<int>(nums.size() + 1));
        for(int i = 0; i < nums.size(); i++) {
            pre[nums[i]][i+1] += 1;
            for(int j = 1; j <= 3; j++) pre[j][i+1] += pre[j][i];
        }
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                for(int k = j; k < n; k++) {
                    int a = pre[1][i+1] - pre[1][0];
                    int b = pre[2][j+1] - pre[2][i];
                    int c = pre[3][n] - pre[3][j];
                    res = min(res, n - a - b - c);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int a = 0, b = 0, c = 0;
        for(int i = 0; i < nums.size(); i++) {
            int aa = a + (nums[i] != 1);
            int bb = min(a,b) + (nums[i] != 2);
            int cc = min({a,b,c}) + (nums[i] != 3);
            a = aa, b = bb, c = cc;
        }
        return min({a,b,c});
    }
};