2826 - Sorting Three Groups

Description (leetcode)

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?

submission

click to reveal

impl Solution {
    pub fn minimum_operations(nums: Vec<i32>) -> i32 {
        // stateful dp
        nums.into_iter()
            // x1, x2, x3 denote the minimal operations to make the array
            // non-decreasing and ends with 1, 2, 3 respectively
            // and they are all 0 for empty array
            .fold([0, 0, 0], |[x1, x2, x3], num| match num {
                // num 1: +1 op for x2 and x3
                1 => [x1, x2 + 1, x3 + 1],
                // num 2: +1 op for x1 and x3, x2 may choose smaller one from x1, x2
                2 => [x1 + 1, x2.min(x1), x3 + 1],
                // num 3: +1 op for x1 and x2, x3 may choose the smallest from x1, x2, x3
                3 => [x1 + 1, x2 + 1, x3.min(x2).min(x1)],
                _ => unreachable!(),
            })
            .into_iter()
            // finally we just pick the smallest one
            .min()
            .unwrap_or_default()
    }
}