#2826

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Sorting Three Groups

Determine the minimum removals to make an array of 1s, 2s, and 3s non-decreasing using dynamic programming transitions.

Problem Statement

Given an integer array nums where each element is either 1, 2, or 3, you can remove any element in a single operation. Your goal is to compute the minimum number of removals required to transform nums into a non-decreasing sequence where all 1s appear before 2s and all 2s appear before 3s.

For example, if nums = [2,1,3,2,1], removing nums[0], nums[2], and nums[3] produces a sorted array [1,1,2], which is non-decreasing. Return the minimum number of such removal operations required for the input array.

Examples

Example 1

Input: nums = [2,1,3,2,1]

Output: 3

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

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

nums is already non-decreasing.

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 3

Solution Approach

Define State Transitions

Model the problem with dynamic programming states dp[i][j] representing the minimum removals for the first i elements ending in group j. Track transitions from group 1 to 2 to 3 while allowing removals if the current element violates the non-decreasing order.

Iterate and Update

Iterate through the array, updating dp values for each possible last group. Remove elements when they break the non-decreasing pattern, and choose the minimum removal cost among valid state transitions. This avoids redundant removal calculations and ensures optimality.

Return Final Answer

After processing all elements, the minimum value among dp[n][1], dp[n][2], and dp[n][3] gives the minimum number of operations needed. This approach directly implements state transition dynamic programming for the three-group sorting pattern.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on tracking three states per array element. Iterating through n elements with constant state updates gives O(n) time and O(1) extra space using rolling states. Full DP table requires O(n*3) space.

What Interviewers Usually Probe

Pay attention to the order of 1s, 2s, and 3s for the DP transitions.
Clarify handling of elements equal to the last group to avoid unnecessary removals.
Consider whether rolling state arrays can optimize space complexity.

Common Pitfalls or Variants

Common pitfalls

Failing to update all three DP states at each step can miss the optimal removal path.
Confusing element equality with a required removal rather than a valid transition.
Attempting greedy removal without considering dynamic programming may overcount operations.

Follow-up variants

Arrays with more than three distinct numbers following a similar state transition DP.
Allowing swap operations instead of removals, adjusting the DP transitions accordingly.
Finding the longest non-decreasing subsequence directly and computing removals as n minus its length.

FAQ

What pattern does Sorting Three Groups follow?

Sorting Three Groups uses state transition dynamic programming, tracking minimum removals for sequences ending in each group.

Can this approach handle arrays longer than 100 elements?

Yes, the DP approach scales linearly with array length, but constraints limit length to 100 in this problem.

Why not use a greedy method to remove elements?

Greedy removal can fail because it does not account for future elements; dynamic programming ensures minimal total removals.

How do equal elements affect DP transitions?

Equal elements can be included without removal if they maintain non-decreasing order, preserving optimal DP states.

Is rolling array optimization necessary?

Rolling arrays reduce space from O(n*3) to O(3), which is efficient for this problem but optional for correctness.

terminal

Solution

Solution 1: 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 $i$th number is changed to $j+1$. The answer is $\min(f[n][0], f[n][1], f[n][2])$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        f = [0] * 3
        for x in nums:
            g = [0] * 3
            if x == 1:
                g[0] = f[0]
                g[1] = min(f[:2]) + 1
                g[2] = min(f) + 1
            elif x == 2:
                g[0] = f[0] + 1
                g[1] = min(f[:2])
                g[2] = min(f) + 1
            else:
                g[0] = f[0] + 1
                g[1] = min(f[:2]) + 1
                g[2] = min(f)
            f = g
        return min(f)

Continue Practicing

#2830 maximize the profit as the salesman #2926 maximum balanced subsequence sum #2713 maximum strictly increasing cells in a matrix