2826. Sorting Three Groups LeetCode Solution

In this guide, you will get 2826. Sorting Three Groups LeetCode Solution with the best time and space complexity. The solution to Sorting Three Groups problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sorting Three Groups solution in C++
Sorting Three Groups solution in Java
Sorting Three Groups solution in Python
Additional Resources

2826. Sorting Three Groups LeetCode Solution image

Problem Statement of Sorting Three Groups

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.

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?

Complexity Analysis

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

2826. Sorting Three Groups LeetCode Solution in C++

class Solution {
 public:
  int minimumOperations(vector<int>& nums) {
    // dp[i] := the longest non-decreasing subsequence so far with numbers in
    // [1..i]
    vector<int> dp(4);

    for (const int num : nums) {
      ++dp[num];
      dp[2] = max(dp[2], dp[1]);
      dp[3] = max(dp[3], dp[2]);
    }

    return nums.size() - dp[3];
  }
};
/* code provided by PROGIEZ */

2826. Sorting Three Groups LeetCode Solution in Java

class Solution {
  public int minimumOperations(List<Integer> nums) {
    // dp[i] := the longest non-decreasing subsequence so far with numbers in [1..i]
    int[] dp = new int[4];

    for (final int num : nums) {
      ++dp[num];
      dp[2] = Math.max(dp[2], dp[1]);
      dp[3] = Math.max(dp[3], dp[2]);
    }

    return nums.size() - dp[3];
  }
}
// code provided by PROGIEZ

2826. Sorting Three Groups LeetCode Solution in Python

class Solution:
  def minimumOperations(self, nums: list[int]) -> int:
    # dp[i] := the longest non-decreasing subsequence so far with numbers in [1..i]
    dp = [0] * 4

    for num in nums:
      dp[num] += 1  # Append num to the sequence so far.
      dp[2] = max(dp[2], dp[1])
      dp[3] = max(dp[3], dp[2])

    return len(nums) - dp[3]
 # code by PROGIEZ