Skip to content

2826. Sorting Three Groups 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  int minimumOperations(vector<int>& nums) {
    // dp[i] := longest non-decreasing subsequence so far with nums 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];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public int minimumOperations(List<Integer> nums) {
    // dp[i] := longest non-decreasing subsequence so far with nums 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];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def minimumOperations(self, nums: List[int]) -> int:
    # dp[i] := longest non-decreasing subsequence so far with nums 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]