Sorting Three Groups solution and explanation
8 more videos on this problem
Leetcode BiWeekly contest 111 - Medium - Sorting Three GroupsPrakhar Agrawal · 16:34 · 2K views
2826. Sorting Three GroupsAyush Rao · 7:32 · 1K views
2826. Sorting Three Groups | Harder Follow-ups | Leetcode Biweekly 111codingMohan · 32:54 · 879 views
6941. Sorting Three Groups || 111th LeetCode Biweekly ContestCoding wale Bhaiya · 0:24 · 756 views
2826. . Sorting Three Groups (Leetcode Medium)Programming Live with Larry · 25:54 · 727 views
【每日一题】LeetCode 2826. Sorting Three GroupsHuifeng Guan · 8:21 · 355 views
[Eng] Leetcode | Biweekly Contest 111 | 2826 Sorting Three GroupsCyCode · 12:10 · 62 views
sorting three groups Leetcode Biweekly 111Cygnatrix · 5:37 · 60 views
Leetcode 2826. Sorting Three Groups (LIS from nlogn to O(n))LetsCode · 8:03 · 29 views
The 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 <= 1001 <= nums[i] <= 3
O(n) time complexity?Approach overview
Problem Overview: You receive an array where every value is 1, 2, or 3. The goal is to modify the minimum number of elements so the array becomes non‑decreasing, meaning all 1s come first, then 2s, then 3s. Each modification lets you change a number to any of the three values.
Approach 1: Greedy Counting Approach (O(n) time, O(1) space)
The final valid array must look like three consecutive segments: 1*, 2*, and 3*. Iterate through the array while counting how many elements violate each segment. For every position, track the minimum changes needed if the current prefix ends in group 1, 2, or 3. This effectively evaluates how many elements must be converted to maintain the sorted grouping. The key idea is that transitions only move forward (1 → 2 → 3), so you maintain running minimum costs rather than exploring all partitions. This greedy counting strategy runs in O(n) time with constant memory and works well because the domain of values is fixed to three groups. The solution relies heavily on simple iteration over an array while maintaining incremental counts.
Approach 2: Dynamic Programming with Subsequence (O(n) time, O(1) space)
Another way to view the task: keep the longest subsequence that already follows the order 1 → 2 → 3. The fewer elements you keep, the more modifications you must perform. Maintain three DP states: dp1 for subsequences ending with 1, dp2 for subsequences ending with 2, and dp3 for subsequences ending with 3. When processing each value, update these states using transitions that preserve the non‑decreasing order. For example, a 2 can extend either a 1 or 2 subsequence. The final answer becomes n - longest_valid_subsequence. This formulation is a compact dynamic programming pattern similar to constrained LIS problems and is easy to extend if the number of groups increases.
Some variations treat the problem as evaluating partition points with prefix counts, which resembles searching optimal boundaries between groups. That perspective connects loosely with prefix scanning techniques often seen in binary search style partition problems.
Recommended for interviews: The dynamic programming state transition is usually what interviewers expect. It shows you recognize the ordered subsequence structure and can maintain minimal states efficiently. The greedy counting formulation is equally optimal and often simpler to implement, but explaining the DP interpretation demonstrates stronger algorithmic reasoning.
Approach 1: Greedy Counting Approach
This approach involves counting the number of each element (1, 2, and 3) and determining the minimum number of deletions needed to rearrange nums so they form a non-decreasing sequence. The problem can be viewed as making three separate groups of numbers, keeping them consecutive to minimize deletions.
We first count the number of 1's, 2's, and 3's. Then, inspect contiguous subsequences of different combinations to find the one that requires the least number of deletions.
def min_operations(nums):
count1 = count2 = count3 = 0
for num in nums:
if num == 1:
count1 += 1
elif num == 2:
count2 += 1
else:
count3 += 1
# Compute the number of deletions needed
operations = float('inf')
for i in range(count1 + 1):
for j in range(count1, count1 + count2 + 1):
to_remove = (sum(num == 1 for num in nums[:i]) +
sum(num == 2 for num in nums[i:j]) +
sum(num == 3 for num in nums[j:count1 + count2 + count3]))
operations = min(operations, to_remove)
return operations
# Example Usage:
print(min_operations([2,1,3,2,1])) # Output: 3
print(min_operations([1,3,2,1,3,3])) # Output: 2
print(min_operations([2,2,2,2,3,3])) # Output: 0#include <stdio.h>
#include <limits.h>
int min_operations(int* nums, int numsSize) {
int count1 = 0, count2 = 0, count3 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 1) count1++;
else if (nums[i] == 2) count2++;
else count3++;
}
int min_operations = INT_MAX;
for (int i = 0; i <= count1; i++) {
int to_remove = i;
int j = count1;
while (j < count1 + count2) {
if (nums[j] != 2) to_remove++;
j++;
}
j = count1 + count2;
while (j < numsSize) {
if (nums[j] != 3) to_remove++;
j++;
}
if (to_remove < min_operations) min_operations = to_remove;
}
return min_operations;
}
// Example Usage:
// int nums[] = {2,1,3,2,1};
// int result = min_operations(nums, 5);
// printf("%d\n", result); // Output: 3The function min_operations counts each occurrence of numbers 1, 2, and 3, then it attempts different configurations of groupings to compute how many operations (removals) are necessary to achieve a non-decreasing order. The complexity of this method allows it to efficiently solve this problem by examining different subarray formations.
Time Complexity: O(n) where n is the length of nums. The operations required are linear in traversing and counting elements.
Space Complexity: O(1) as we use only a fixed amount of extra space for counting.
Approach 2: Dynamic Programming with Subsequence
This approach is based on converting nums into the longest non-decreasing subsequence using dynamic programming techniques. We determine the parts of the sequence that need elimination to create the desired subsequence. The task is to minimize the deletions so that the subsequence becomes non-decreasing.
By maintaining an auxiliary array to store the longest increasing subsequence ending at each position and using binary search, the removal count calculations are optimized.
#include <vector>
#include <algorithm>
int minOperations(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] >= nums[j]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
}
int lisLength = *std::max_element(dp.begin(), dp.end());
return n - lisLength;
}
// Example Usage:
// std::vector<int> nums = {2,1,3,2,1};
// int result = minOperations(nums);
// std::cout << result << std::endl; // Output: 3function minOperations(nums) {
const n = nums.length;
const dp = Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] >= nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
const lisLength = Math.max(...dp);
return n - lisLength;
}
// Example Usage:
console.log(minOperations([2,1,3,2,1])); // Output: 3
console.log(minOperations([1,3,2,1,3,3])); // Output: 2
console.log(minOperations([2,2,2,2,3,3])); // Output: 0This C++ implementation relies on the same dynamic programming technique to determine the longest increasing subsequence. By updating each position with the maximum subsequence length that can be formed up to that point, it then calculates the remainder to derive the deletions required.
Time Complexity: O(n^2), where n is the length of nums, due to nested loops.
Space Complexity: O(n) for the dp array.
Approach 3: Dynamic Programming
We define f[i][j] as the minimum number of operations to turn the first i numbers into a beautiful array, and the ith number is changed to j+1. The answer is min(f[n][0], f[n][1], f[n][2]).
We can enumerate all cases where the ith number is changed to j+1, and then take the minimum value. Here, we can use a rolling array to optimize the space complexity.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
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]));
}
}function minimumOperations(nums: number[]): number {
let f: number[] = new Array(3).fill(0);
for (const x of nums) {
const g: number[] = new Array(3).fill(0);
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);
}func minimumOperations(nums []int) int {
f := make([]int, 3)
for _, x := range nums {
g := make([]int, 3)
if x == 1 {
g[0] = f[0]
g[1] = min(f[0], f[1]) + 1
g[2] = min(f[0], min(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 = g
}
return min(f[0], min(f[1], f[2]))
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Counting Approach | Time Complexity: O(n) where n is the length of nums. The operations required are linear in traversing and counting elements. |
| Dynamic Programming with Subsequence | Time Complexity: O(n^2), where n is the length of nums, due to nested loops. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Counting Approach | O(n) | O(1) | Best when values are limited to three groups and you want a simple linear pass with minimal state. |
| Dynamic Programming with Subsequence | O(n) | O(1) | Preferred in interviews to demonstrate ordered subsequence DP reasoning similar to LIS problems. |
Frequently asked questions
Is Sorting Three Groups easy or hard?
Sorting Three Groups is rated Medium on LeetCode with an acceptance rate around 43%. The implementation is short, but recognizing the ordered subsequence or minimal partition idea requires some experience with dynamic programming patterns.
Sorting Three Groups Python/Java solution
Python, Java, C++, and JavaScript implementations typically maintain three variables representing the minimal changes for groups ending in 1, 2, or 3. Each element updates these values using simple comparisons, producing an O(n) time and O(1) space solution.
How to solve Sorting Three Groups in O(n)?
Track the minimum operations needed if the prefix ends with group 1, 2, or 3. While iterating through the array, update these states based on whether the current value matches the expected group. Because transitions only move forward (1→2→3), the algorithm requires only a single pass and constant space.
What is the best approach for Sorting Three Groups?
The most common solution uses dynamic programming with three states representing subsequences ending in 1, 2, or 3. Each element updates these states while preserving the order 1 → 2 → 3. This runs in O(n) time and O(1) space and clearly models the constraint that the final array must be non‑decreasing.
Is Sorting Three Groups asked at Google/Amazon/Meta?
Problems involving grouped ordering and subsequence dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often ask for minimum edits to enforce ordering constraints or longest subsequences with restricted values.
What data structure is used in Sorting Three Groups?
The problem mainly uses arrays and a few integer counters or DP variables. No advanced data structures are required. The core idea relies on dynamic programming states or prefix counting while iterating through the array.
What is the time complexity of Sorting Three Groups?
Optimal solutions run in O(n) time where n is the length of the array. Both the greedy counting method and the DP subsequence approach scan the array once while maintaining a few counters or DP states. Space complexity is O(1).