Sorting Three Groups

• 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 1s.
• Inside this loop, use another loop to iterate j from i to n. This j represents the boundary after which we no longer keep 2s.
• 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 1s.
  • A fourth loop iterates from k = i to j-1 to count the 2s.
  • A fifth loop iterates from k = j to n-1 to count the 3s.
• Update maxKept = Math.max(maxKept, currentKept).
• After all loops complete, the minimum number of removals is n - maxKept.

The core idea is to exhaustively check every possible structure of the final sorted array. A non-decreasing array of 1s, 2s, and 3s must be of the form [1,...,1, 2,...,2, 3,...,3]. This structure can be defined by two boundaries: one where the 1s end and 2s begin, and another where the 2s end and 3s 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 1s in the first segment.
• Count the number of 2s in the second segment.
• Count the number of 3s 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.

1class Solution {2    public int minimumOperations(int[] nums) {3        int n = nums.length;4        int maxKept = 0;5 6        // i is the split point before which we only keep 1s7        // j is the split point before which we only keep 1s or 2s8        for (int i = 0; i <= n; i++) {9            for (int j = i; j <= n; j++) {10                int currentKept = 0;11                // Count 1s in the first part [0, i-1]12                for (int k = 0; k < i; k++) {13                    if (nums[k] == 1) {14                        currentKept++;15                    }16                }17                // Count 2s in the second part [i, j-1]18                for (int k = i; k < j; k++) {19                    if (nums[k] == 2) {20                        currentKept++;21                    }22                }23                // Count 3s in the third part [j, n-1]24                for (int k = j; k < n; k++) {25                    if (nums[k] == 3) {26                        currentKept++;27                    }28                }29                maxKept = Math.max(maxKept, currentKept);30            }31        }32        return n - maxKept;33    }34}

• 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 1s 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.

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 1s, 2s, and 3s.

• prefixOnes[k] will store the total count of 1s in nums[0...k-1].
• prefixTwos[k] will store the total count of 2s in nums[0...k-1].
• prefixThrees[k] will store the total count of 3s 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 2s 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²).

1class Solution {2    public int minimumOperations(int[] nums) {3        int n = nums.length;4        int[] prefixOnes = new int[n + 1];5        int[] prefixTwos = new int[n + 1];6        int[] prefixThrees = new int[n + 1];7 8        for (int i = 0; i < n; i++) {9            prefixOnes[i + 1] = prefixOnes[i] + (nums[i] == 1 ? 1 : 0);10            prefixTwos[i + 1] = prefixTwos[i] + (nums[i] == 2 ? 1 : 0);11            prefixThrees[i + 1] = prefixThrees[i] + (nums[i] == 3 ? 1 : 0);12        }13 14        int maxKept = 0;15        for (int i = 0; i <= n; i++) {16            for (int j = i; j <= n; j++) {17                int keptOnes = prefixOnes[i];18                int keptTwos = prefixTwos[j] - prefixTwos[i];19                int keptThrees = prefixThrees[n] - prefixThrees[j];20                maxKept = Math.max(maxKept, keptOnes + keptTwos + keptThrees);21            }22        }23        return n - maxKept;24    }25}

• 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).

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 1s, followed by zero or more 2s, followed by zero or more 3s.

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 1s.
• len2: The length of the longest non-decreasing subsequence seen so far that consists of 1s and 2s, 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 1s. So, we increment len1.
• If num is 2: It can start a new sequence of 2s after a sequence of 1s (length len1 + 1) or extend an existing sequence of 2s (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.

1class Solution {2    public int minimumOperations(int[] nums) {3        int n = nums.length;4        // len1: length of LIS ending with 15        // len2: length of LIS ending with 26        // len3: length of LIS ending with 37        int len1 = 0, len2 = 0, len3 = 0;8 9        for (int num : nums) {10            if (num == 1) {11                len1++;12            } else if (num == 2) {13                len2 = Math.max(len1, len2) + 1;14            } else { // num == 315                len3 = Math.max(len1, Math.max(len2, len3)) + 1;16            }17        }18        19        // The length of the longest non-decreasing subsequence is the max of the lengths of subsequences ending in 1, 2, or 3.20        // Note that a sequence of only 1s is a valid non-decreasing subsequence.21        int maxLen = Math.max(len1, Math.max(len2, len3));22        return n - maxLen;23    }24}