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

Description Hints 3 Solution Video 16:34

2826. Sorting Three Groups

Medium43.5% acceptance1 company

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?

Asked at 1 company

UiPath

Topics

Hints open one at a time

Hint 1

The problem asks to change the array nums to make it sorted (i.e., all the 1s are on the left of 2s, and all the 2s are on the left of 3s.).

Hint 2

We can try all the possibilities to make nums indices range in [0, i) to 0 and [i, j) to 1 and [j, n) to 2. Note the ranges are left-close and right-open; each might be empty. Namely, 0 <= i <= j <= n.

Hint 3

Count the changes we need for each possibility by comparing the expected and original values at each index position.

16:34

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minimumOperations(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,1,3,2,1]

Input

[1,3,2,1,3,3]

Input

[2,2,2,2,3,3]

Your code is saved on this device.Solution