Sorting Three Groups - Practice Coding Problems

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.

A non-decreasing array means that for all valid indices i, nums[i] <= nums[i+1].

Input & Output

Example 1 — Mixed Values

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

› Output: 3

💡 Note: One optimal non-decreasing subsequence is [1,2] or [1,3]. We keep 2 elements and remove 3: operations = 5 - 2 = 3

Example 2 — Already Sorted

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

› Output: 2

💡 Note: Longest non-decreasing subsequence could be [1,1,3,3] with length 4. Remove 2 elements: operations = 6 - 4 = 2

Example 3 — All Same

$ Input: nums = [2,2,2,2]

› Output: 0

💡 Note: Array is already non-decreasing (all elements equal), so no operations needed

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is 1, 2, or 3

Visualization

Tap to expand

Understanding the Visualization

Input Array

Mixed array with values 1, 2, 3 that needs sorting

Find LIS

Identify longest non-decreasing subsequence to keep

Remove Rest

Remove all elements not in optimal subsequence

Key Takeaway

🎯 Key Insight: Instead of thinking about sorting, find the longest subsequence that's already sorted and remove everything else

Asked in

G Google 25 f Meta 18 a Amazon 15 M Microsoft 12

The key insight is to find the longest non-decreasing subsequence and remove everything else. Since values are only 1, 2, 3, we can optimize by tracking the best subsequence length ending with each value. Best approach uses optimized DP in O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - LIS Approach	O(n²)	O(n)	Find longest non-decreasing subsequence using dynamic programming
Brute Force - Try All Subsequences	O(2^n)	O(n)	Generate all possible subsequences and find longest non-decreasing one
Optimized - Count-Based DP	O(n)	O(1)	Use the constraint that values are only 1, 2, 3 for O(n) solution

Dynamic Programming - LIS Approach — Algorithm Steps

Create DP array where dp[i] = length of longest non-decreasing subsequence ending at index i
For each element, check all previous elements ≤ current
Update dp[i] with maximum possible length
Return n - max(dp)

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize DP

Each position starts with length 1 (itself)

Fill DP Table

For each position, check all previous smaller/equal values

Find Maximum

Maximum DP value is longest subsequence length

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    if (numsSize == 0) return 0;
    
    // dp[i] = length of longest non-decreasing subsequence ending at index i
    int* dp = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        dp[i] = 1;
    }
    
    for (int i = 1; i < numsSize; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] <= nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    
    // Find maximum length
    int maxLength = 0;
    for (int i = 0; i < numsSize; i++) {
        if (dp[i] > maxLength) {
            maxLength = dp[i];
        }
    }
    
    free(dp);
    return numsSize - maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops: outer loop iterates n times, inner loop up to n times for each position

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores one value per input element

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming - LIS Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler