Sorting Three Groups

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.

Examples

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?

Solution

Method 1 - Dynamic Programming

Intuition

To minimize removals, we want to keep the maximum number of elements that can form a non-decreasing subsequence. The minimum operations = total length - length of longest non-decreasing subsequence.

Approach

1. Use DP where dp[i][j] represents the maximum length of non-decreasing subsequence ending at index i with value j
2. For each element, we can either keep it (if it maintains non-decreasing order) or skip it
3. Transition: dp[i][nums[i]] = max(dp[i-1][k] + 1) for all valid k <= nums[i]
4. Return n - max(dp[i][j]) for all valid i, j

Code

C++

#include <vector>
#include <algorithm>
using namespace std;

int minimumOperations(vector<int>& nums) {
    int n = nums.size();
    // dp[i][j] = max length of non-decreasing subsequence ending at index i with value j
    vector<vector<int>> dp(n, vector<int>(4, 0));
    
    // Base case
    dp[0][nums[0]] = 1;
    
    for (int i = 1; i < n; i++) {
        // Copy previous state (skip current element)
        for (int j = 1; j <= 3; j++) {
            dp[i][j] = dp[i-1][j];
        }
        
        // Include current element
        int maxPrev = 0;
        for (int j = 1; j <= nums[i]; j++) {
            maxPrev = max(maxPrev, dp[i-1][j]);
        }
        dp[i][nums[i]] = max(dp[i][nums[i]], maxPrev + 1);
    }
    
    int maxLen = 0;
    for (int j = 1; j <= 3; j++) {
        maxLen = max(maxLen, dp[n-1][j]);
    }
    
    return n - maxLen;
}

Go

func minimumOperations(nums []int) int {
    n := len(nums)
    // dp[i][j] = max length ending at index i with value j
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, 4)
    }
    
    dp[0][nums[0]] = 1
    
    for i := 1; i < n; i++ {
        // Copy previous state
        for j := 1; j <= 3; j++ {
            dp[i][j] = dp[i-1][j]
        }
        
        // Include current element
        maxPrev := 0
        for j := 1; j <= nums[i]; j++ {
            if dp[i-1][j] > maxPrev {
                maxPrev = dp[i-1][j]
            }
        }
        if maxPrev + 1 > dp[i][nums[i]] {
            dp[i][nums[i]] = maxPrev + 1
        }
    }
    
    maxLen := 0
    for j := 1; j <= 3; j++ {
        if dp[n-1][j] > maxLen {
            maxLen = dp[n-1][j]
        }
    }
    
    return n - maxLen
}

Java

class Solution {
    public int minimumOperations(int[] nums) {
        int n = nums.length;
        // dp[i][j] = max length of non-decreasing subsequence ending at index i with value j
        int[][] dp = new int[n][4];
        
        dp[0][nums[0]] = 1;
        
        for (int i = 1; i < n; i++) {
            // Copy previous state (skip current element)
            for (int j = 1; j <= 3; j++) {
                dp[i][j] = dp[i-1][j];
            }
            
            // Include current element
            int maxPrev = 0;
            for (int j = 1; j <= nums[i]; j++) {
                maxPrev = Math.max(maxPrev, dp[i-1][j]);
            }
            dp[i][nums[i]] = Math.max(dp[i][nums[i]], maxPrev + 1);
        }
        
        int maxLen = 0;
        for (int j = 1; j <= 3; j++) {
            maxLen = Math.max(maxLen, dp[n-1][j]);
        }
        
        return n - maxLen;
    }
}

Kotlin

class Solution {
    fun minimumOperations(nums: IntArray): Int {
        val n = nums.size
        // dp[i][j] = max length ending at index i with value j
        val dp = Array(n) { IntArray(4) }
        
        dp[0][nums[0]] = 1
        
        for (i in 1 until n) {
            // Copy previous state
            for (j in 1..3) {
                dp[i][j] = dp[i-1][j]
            }
            
            // Include current element
            var maxPrev = 0
            for (j in 1..nums[i]) {
                maxPrev = maxOf(maxPrev, dp[i-1][j])
            }
            dp[i][nums[i]] = maxOf(dp[i][nums[i]], maxPrev + 1)
        }
        
        var maxLen = 0
        for (j in 1..3) {
            maxLen = maxOf(maxLen, dp[n-1][j])
        }
        
        return n - maxLen
    }
}

Python

def minimumOperations(nums: list[int]) -> int:
    n = len(nums)
    # dp[i][j] = max length of non-decreasing subsequence ending at index i with value j
    dp = [[0] * 4 for _ in range(n)]
    
    dp[0][nums[0]] = 1
    
    for i in range(1, n):
        # Copy previous state (skip current element)
        for j in range(1, 4):
            dp[i][j] = dp[i-1][j]
        
        # Include current element
        max_prev = 0
        for j in range(1, nums[i] + 1):
            max_prev = max(max_prev, dp[i-1][j])
        dp[i][nums[i]] = max(dp[i][nums[i]], max_prev + 1)
    
    max_len = max(dp[n-1][j] for j in range(1, 4))
    return n - max_len

Rust

pub fn minimum_operations(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // dp[i][j] = max length ending at index i with value j
    let mut dp = vec![vec![0; 4]; n];
    
    dp[0][nums[0] as usize] = 1;
    
    for i in 1..n {
        // Copy previous state
        for j in 1..=3 {
            dp[i][j] = dp[i-1][j];
        }
        
        // Include current element
        let mut max_prev = 0;
        for j in 1..=nums[i] as usize {
            max_prev = max_prev.max(dp[i-1][j]);
        }
        let curr_val = nums[i] as usize;
        dp[i][curr_val] = dp[i][curr_val].max(max_prev + 1);
    }
    
    let max_len = (1..=3).map(|j| dp[n-1][j]).max().unwrap_or(0);
    (n as i32) - (max_len as i32)
}

TypeScript

function minimumOperations(nums: number[]): number {
    const n = nums.length;
    // dp[i][j] = max length of non-decreasing subsequence ending at index i with value j
    const dp: number[][] = Array(n).fill(null).map(() => Array(4).fill(0));
    
    dp[0][nums[0]] = 1;
    
    for (let i = 1; i < n; i++) {
        // Copy previous state (skip current element)
        for (let j = 1; j <= 3; j++) {
            dp[i][j] = dp[i-1][j];
        }
        
        // Include current element
        let maxPrev = 0;
        for (let j = 1; j <= nums[i]; j++) {
            maxPrev = Math.max(maxPrev, dp[i-1][j]);
        }
        dp[i][nums[i]] = Math.max(dp[i][nums[i]], maxPrev + 1);
    }
    
    let maxLen = 0;
    for (let j = 1; j <= 3; j++) {
        maxLen = Math.max(maxLen, dp[n-1][j]);
    }
    
    return n - maxLen;
}

Complexity

• ⏰ Time complexity: O(n) since we have at most 3 values to consider at each step
• 🧺 Space complexity: O(n) for the DP table (can be optimized to O(1) using rolling array)