LeetCode Problem 2826

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Dynamic Programming

Solution

LeetCode 2826 - Sorting Three Groups

Problem Understanding

We are given an array nums where every element is either 1, 2, or 3. In one operation, we may remove any element from the array. Our goal is to make the remaining array non-decreasing while performing the minimum possible number of removals.

A non-decreasing array means that every element is less than or equal to the element that comes after it. Since the array contains only the values 1, 2, and 3, any valid final array must have all remaining 1s before all remaining 2s, and all remaining 2s before all remaining 3s. Some groups may be empty. For example:

• [1,1,2,2,3] is valid.
• [1,1,3,3] is valid because the 2 group is empty.
• [2,2,3] is valid because the 1 group is empty.
• [1,3,2] is not valid because a 2 appears after a 3.

The key observation is that removing elements preserves the relative order of the remaining elements. Therefore, we are effectively looking for the largest subsequence that is already non-decreasing. Once we know the length of the longest non-decreasing subsequence, every other element must be removed.

The constraints are very small:

• 1 <= nums.length <= 100
• nums[i] ∈ {1,2,3}

Even an O(n²) solution easily fits within these limits. However, the follow-up asks whether an O(n) solution is possible, suggesting that the special nature of having only three distinct values can be exploited.

Some important edge cases include:

• Arrays already sorted, requiring zero removals.
• Arrays sorted in strictly decreasing order.
• Arrays containing only one distinct value.
• Arrays where one or two groups are completely absent.
• Very short arrays of length 1.

Approaches

Brute Force

A brute force solution would examine every possible subsequence of the array and check whether it is non-decreasing. Among all valid subsequences, we would keep the longest one.

This approach is correct because every valid final array is a subsequence of the original array. By finding the longest valid subsequence, we minimize the number of removed elements.

However, an array of length n has 2ⁿ subsequences. Checking all of them becomes infeasible even for moderate values of n, making this approach impractical.

Key Insight

Since removals preserve order, the problem is equivalent to finding the length of the Longest Non-Decreasing Subsequence (LNDS).

If the longest non-decreasing subsequence has length L, then:

minimum removals = n - L

Because every element not belonging to that subsequence must be removed.

The special property of this problem is that values are restricted to {1,2,3}. Instead of using a general LNDS algorithm, we can use dynamic programming with only three states.

Let:

• dp1 = longest valid subsequence ending in group 1
• dp2 = longest valid subsequence ending in group 2
• dp3 = longest valid subsequence ending in group 3

As we process each number, we update the appropriate state while preserving non-decreasing order.

This produces an O(n) solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2ⁿ · n)	O(n)	Enumerates every subsequence
Optimal DP	O(n)	O(1)	Uses three DP states corresponding to values 1, 2, and 3

Algorithm Walkthrough

Optimal Dynamic Programming

1. Initialize three variables:

• dp1 = 0
• dp2 = 0
• dp3 = 0

Each variable represents the maximum length of a valid non-decreasing subsequence ending with that value. 2. Process the array from left to right. 3. If the current number is 1, it can only extend a sequence ending with 1.

dp1 = dp1 + 1

4. If the current number is 2, it can extend either:

• a sequence ending with 1, or
• a sequence ending with 2

Therefore:

dp2 = max(dp1, dp2) + 1

5. If the current number is 3, it can extend:

• a sequence ending with 1
• a sequence ending with 2
• a sequence ending with 3

Therefore:

dp3 = max(dp1, dp2, dp3) + 1

6. Continue until all elements have been processed.
7. The longest non-decreasing subsequence length is:

longest = max(dp1, dp2, dp3)

8. Return:

len(nums) - longest

Why it works

At any point during the scan, dp1, dp2, and dp3 store the maximum lengths of valid non-decreasing subsequences whose last value is 1, 2, and 3 respectively. When a new value arrives, we extend only those states that maintain non-decreasing order. Since every valid subsequence must end in one of the three values, the maximum among these states after processing all elements equals the length of the longest non-decreasing subsequence. Removing every element outside that subsequence yields the minimum number of operations.

Python Solution

from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        dp1 = 0
        dp2 = 0
        dp3 = 0

        for num in nums:
            if num == 1:
                dp1 += 1
            elif num == 2:
                dp2 = max(dp1, dp2) + 1
            else:  # num == 3
                dp3 = max(dp1, dp2, dp3) + 1

        longest = max(dp1, dp2, dp3)
        return len(nums) - longest

The implementation maintains exactly the three DP states described in the algorithm. As each value is processed, the corresponding state is updated according to the largest compatible subsequence seen so far.

For a value 1, only sequences ending with 1 may be extended. For a value 2, both 1 and 2 ending sequences are valid predecessors. For a value 3, any previous state is valid because 3 is the largest possible value.

After processing the entire array, the maximum of the three states gives the longest non-decreasing subsequence length. Subtracting that value from the array length yields the minimum number of removals.

Go Solution

func minimumOperations(nums []int) int {
	dp1, dp2, dp3 := 0, 0, 0

	for _, num := range nums {
		if num == 1 {
			dp1++
		} else if num == 2 {
			if dp1 > dp2 {
				dp2 = dp1 + 1
			} else {
				dp2 = dp2 + 1
			}
		} else {
			best := dp1
			if dp2 > best {
				best = dp2
			}
			if dp3 > best {
				best = dp3
			}
			dp3 = best + 1
		}
	}

	longest := dp1
	if dp2 > longest {
		longest = dp2
	}
	if dp3 > longest {
		longest = dp3
	}

	return len(nums) - longest
}

The Go implementation mirrors the Python version exactly. Since the values are very small and the array length is at most 100, integer overflow is not a concern. The solution uses only three integer variables, resulting in constant extra space. Go slices are processed directly with a range loop, and no additional data structures are required.

Worked Examples

Example 1

Input

[2,1,3,2,1]

Step	Value	dp1	dp2	dp3
Start	-	0	0	0
1	2	0	1	0
2	1	1	1	0
3	3	1	1	2
4	2	1	2	2
5	1	2	2	2

Final values:

longest = 2
answer = 5 - 2 = 3

Example 2

Input

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

Step	Value	dp1	dp2	dp3
Start	-	0	0	0
1	1	1	0	0
2	3	1	0	2
3	2	1	2	2
4	1	2	2	2
5	3	2	2	3
6	3	2	2	4

Final values:

longest = 4
answer = 6 - 4 = 2

Example 3

Input

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

Step	Value	dp1	dp2	dp3
Start	-	0	0	0
1	2	0	1	0
2	2	0	2	0
3	2	0	3	0
4	2	0	4	0
5	3	0	4	5
6	3	0	4	6

Final values:

longest = 6
answer = 6 - 6 = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is processed exactly once
Space	O(1)	Only three DP variables are stored

The algorithm performs a single left-to-right scan through the array. Every iteration updates a constant number of variables, resulting in linear time complexity. No auxiliary arrays or collections are required, so the extra space usage remains constant.

Test Cases

sol = Solution()

assert sol.minimumOperations([2, 1, 3, 2, 1]) == 3  # example 1
assert sol.minimumOperations([1, 3, 2, 1, 3, 3]) == 2  # example 2
assert sol.minimumOperations([2, 2, 2, 2, 3, 3]) == 0  # example 3

assert sol.minimumOperations([1]) == 0  # single element
assert sol.minimumOperations([2]) == 0  # single element value 2
assert sol.minimumOperations([3]) == 0  # single element value 3

assert sol.minimumOperations([1, 1, 1, 1]) == 0  # all ones
assert sol.minimumOperations([2, 2, 2]) == 0  # all twos
assert sol.minimumOperations([3, 3, 3]) == 0  # all threes

assert sol.minimumOperations([3, 2, 1]) == 2  # strictly decreasing
assert sol.minimumOperations([3, 3, 2, 2, 1, 1]) == 4  # large decreasing blocks

assert sol.minimumOperations([1, 2, 3]) == 0  # already sorted
assert sol.minimumOperations([1, 1, 2, 2, 3, 3]) == 0  # perfect grouping

assert sol.minimumOperations([2, 1]) == 1  # smallest inversion
assert sol.minimumOperations([3, 1, 2]) == 1  # remove leading 3
assert sol.minimumOperations([1, 3, 2]) == 1  # remove 3 or 2

assert sol.minimumOperations([1, 2, 1, 2, 1, 2]) == 2  # alternating 1 and 2
assert sol.minimumOperations([3, 1, 3, 1, 3, 1]) == 3  # alternating 3 and 1

Test Summary

Test	Why
[2,1,3,2,1]	Official example
[1,3,2,1,3,3]	Official example
[2,2,2,2,3,3]	Already valid
[1]	Minimum size input
[2]	Single element value 2
[3]	Single element value 3
[1,1,1,1]	Single group only
[2,2,2]	Single group only
[3,3,3]	Single group only
[3,2,1]	Strictly decreasing
[3,3,2,2,1,1]	Large decreasing blocks
[1,2,3]	Already sorted
[1,1,2,2,3,3]	Perfect grouping
[2,1]	Small inversion
[3,1,2]	Leading large value
[1,3,2]	Middle inversion
[1,2,1,2,1,2]	Alternating pattern
[3,1,3,1,3,1]	Multiple conflicting groups

Edge Cases

Array Already Non-Decreasing

Arrays such as [1,1,2,2,3,3] already satisfy the required ordering. A common mistake is to perform unnecessary removals due to incorrect state transitions. In this implementation, every element extends a valid subsequence, so the longest non-decreasing subsequence equals the entire array length, producing an answer of 0.

Array Contains Only One Value

Arrays like [2,2,2,2] contain only a single group. Since equal values are allowed in a non-decreasing sequence, no removals are necessary. The DP correctly accumulates the corresponding state while leaving the others unchanged.

Strictly Decreasing Array

For an array such as [3,2,1], the longest non-decreasing subsequence has length 1. A naive implementation might incorrectly attempt to keep multiple elements. The DP formulation naturally enforces valid ordering constraints and identifies that only one element can remain, yielding 3 - 1 = 2 removals.

Missing Intermediate Groups

Arrays such as [1,1,3,3] contain no 2s. The problem does not require all three groups to exist. The DP transitions allow a sequence to move directly from 1 to 3, so the entire array is preserved and the answer remains 0.

Very Small Inputs

When n = 1, every array is automatically non-decreasing. The algorithm initializes all states to zero and updates exactly one state during processing, producing a longest subsequence length of 1 and an answer of 0. This avoids boundary-related bugs that sometimes occur in DP solutions.