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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sorting Three Groups

Number: 2904

Difficulty: Medium

Paid? No

Companies: UiPath

Problem Description

Given an integer array nums where each element is 1, 2, or 3, the goal is to make nums non-decreasing by removing the minimum number of elements. A non-decreasing array in this scenario means that all 1's (if any) appear first, followed by 2's, and then 3's. You must decide which elements to remove such that the overall sequence becomes sorted in non-decreasing order, while minimizing the removals.

Key Insights

  • The target non-decreasing order is: first a block of 1's, then 2's, and finally 3's.
  • Instead of focusing on removals, we can focus on retaining the longest subsequence that already follows this order.
  • This problem is equivalent to finding the maximum subsequence (not necessarily contiguous) that is non-decreasing.
  • Use dynamic programming with three states representing the segments (for 1's, then 2's, then 3's).
  • The minimum operations required equals the array length minus the length of the longest valid subsequence.

Space and Time Complexity

Time Complexity: O(n) – we iterate over the array once updating our DP states in constant time. Space Complexity: O(1) – we maintain only three counters for the DP approach.

Solution

We solve the problem using a dynamic programming approach with three states:

  1. dp1: Maximum length of a subsequence that contains only 1's.
  2. dp2: Maximum length of a subsequence that is non-decreasing and can include 1's followed by 2's.
  3. dp3: Maximum length of a subsequence that is non-decreasing and can include 1's, then 2's, then 3's.

For each element:

  • If the element is 1, it can extend the dp1 subsequence.
  • If the element is 2, it can either start a new segment after dp1 or extend the current dp2, so dp2 is updated to the maximum of (dp1 and dp2) plus one.
  • If the element is 3, it can only be appended if a valid dp2 or dp3 sequence exists, hence dp3 is updated to max(dp2, dp3) plus one.

Finally, the maximum valid subsequence length is max(dp1, dp2, dp3) and the answer is the total number of elements minus this value.

Code Solutions

# Python solution for Sorting Three Groups

def min_removals_to_nondecreasing(nums):
    # dp1: longest subsequence ending with 1's
    # dp2: longest subsequence following 1's then 2's
    # dp3: longest subsequence following 1's, 2's, then 3's
    dp1 = 0
    dp2 = 0
    dp3 = 0

    # Iterate over each element in nums
    for num in nums:
        if num == 1:
            # Append current 1 to dp1 subsequence
            dp1 += 1
        elif num == 2:
            # For a 2, it could either start after a sequence of 1's or extend the current 2's sequence
            dp2 = max(dp1, dp2) + 1
        elif num == 3:
            # For a 3, append to the best valid sequence from dp2 or dp3
            dp3 = max(dp2, dp3) + 1

    # The maximum valid subsequence we can retain
    longest_valid_subseq = max(dp1, dp2, dp3)
    # The minimum removals is the total elements minus the length of the valid subsequence
    return len(nums) - longest_valid_subseq

# Example usage:
print(min_removals_to_nondecreasing([2,1,3,2,1]))  # Expected output: 3
print(min_removals_to_nondecreasing([1,3,2,1,3,3]))  # Expected output: 2
print(min_removals_to_nondecreasing([2,2,2,2,3,3]))  # Expected output: 0
← Back to All Questions