We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sorting Three Groups

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires us to rearrange the elements of the array into a non-decreasing order by removing the minimum number of elements.
  • Since the elements can only be 1, 2, or 3, we can use a frequency count to determine how many of each element we have.
  • The challenge is to find the longest subsequence of 1s, 2s, and 3s that can remain in the array while still being non-decreasing.
  • We can utilize dynamic programming to maintain counts of valid subsequences as we traverse the array.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will traverse the nums array while maintaining counts of the longest valid subsequences that can be formed with the numbers 1, 2, and 3. We will use three counters:

  • count1: counts the number of 1s in the valid subsequence.
  • count2: counts the number of 2s that can follow the 1s.
  • count3: counts the number of 3s that can follow the 2s.

At the end, the minimum number of operations required will be the total number of elements minus the length of the longest valid subsequence.

Code Solutions

def min_operations(nums):
    count1 = count2 = count3 = 0
    
    for num in nums:
        if num == 1:
            count1 += 1
        elif num == 2:
            count2 = max(count2 + 1, count1)
        elif num == 3:
            count3 = max(count3 + 1, count2)
    
    # Total elements minus the longest valid subsequence
    return len(nums) - count3

# Example usage
print(min_operations([2, 1, 3, 2, 1]))  # Output: 3
← Back to All Questions