Problem Description

You are given an integer array nums where each element is either 1, 2, or 3. Your goal is to make the array non-decreasing (each element is less than or equal to the next element) by removing some elements.

In each operation, you can remove one element from nums. You need to find the minimum number of operations (removals) required to make the remaining array non-decreasing.

For example:

• If nums = [2, 1, 3, 2], you could remove the elements at indices 0 and 3 to get [1, 3], which is non-decreasing. This takes 2 operations.
• A non-decreasing array means that for any two adjacent elements, the left element is less than or equal to the right element (like [1, 1, 2, 3, 3]).

The solution uses dynamic programming where f[j] represents the minimum number of operations needed to process all elements seen so far, with the last kept element being j+1. For each new element x in the array, we calculate:

• If we keep x as value 1, we need all previous elements to be ≤ 1
• If we keep x as value 2, we need all previous elements to be ≤ 2
• If we keep x as value 3, we need all previous elements to be ≤ 3
• If the current element doesn't match the target value, we add 1 to the operation count (meaning we remove it)

The final answer is the minimum value among all possible ending states.

Intuition

The key insight is that since we can only remove elements (not rearrange them), we're essentially choosing which elements to keep from the original array while maintaining their relative order. For the kept elements to form a non-decreasing sequence, each kept element must be greater than or equal to all previously kept elements.

Since each element can only be 1, 2, or 3, we can think about this problem differently: at any position in the array, the "last kept value" can only be one of these three numbers. This limited state space makes dynamic programming feasible.

The crucial observation is that if we've processed some prefix of the array and the last element we kept was value k, then for the remaining array to be non-decreasing, we can only keep future elements that are ≥ k.

This leads us to track three states as we process each element:

• The minimum operations needed if the last kept element is 1
• The minimum operations needed if the last kept element is 2
• The minimum operations needed if the last kept element is 3

For each new element x, we have a choice: either keep it or remove it. If we keep it, it becomes our new "last kept element". If we remove it, we add 1 to our operation count and maintain the previous "last kept element".

The transition works as follows: if we want the current element to be our new last kept value j, we need the previous last kept value to be ≤ j. So we look at all valid previous states (values ≤ j) and take the minimum operations from those states. If the current element x doesn't equal j, we add 1 (meaning we remove the current element).

By processing the entire array this way and tracking the minimum operations for each possible ending value, we can find the overall minimum operations needed.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

The solution uses dynamic programming with state compression to optimize space complexity. Let's walk through the implementation step by step.

We maintain an array f of size 3, where f[j] represents the minimum number of operations needed to process all elements seen so far, with the last kept element being j+1.

Initially, f = [0, 0, 0] since we haven't processed any elements yet.

For each element x in nums, we create a new state array g to store the updated minimum operations:

Case 1: When x == 1

• g[0] = f[0]: If we want the last kept element to be 1, and the current element is 1, we keep it without any additional operations
• g[1] = min(f[:2]) + 1: If we want the last kept element to be 2, but current is 1, we must remove the current element (add 1 operation)
• g[2] = min(f) + 1: If we want the last kept element to be 3, but current is 1, we must remove the current element

Case 2: When x == 2

• g[0] = f[0] + 1: If we want the last kept element to be 1, but current is 2, we must remove it (2 > 1 violates non-decreasing)
• g[1] = min(f[:2]): If we want the last kept element to be 2, and current is 2, we can keep it. Previous state can be 1 or 2
• g[2] = min(f) + 1: If we want the last kept element to be 3, but current is 2, we must remove it

Case 3: When x == 3

• g[0] = f[0] + 1: If we want the last kept element to be 1, but current is 3, we must remove it
• g[1] = min(f[:2]) + 1: If we want the last kept element to be 2, but current is 3, we must remove it
• g[2] = min(f): If we want the last kept element to be 3, and current is 3, we can keep it. Previous state can be 1, 2, or 3

After processing each element, we update f = g to carry forward the state.

The key pattern here is:

• When the current element equals our target last value, we don't add to the operation count
• When they differ, we add 1 (removing the current element)
• We use min(f[:k]) to find the best previous state that maintains the non-decreasing property

Finally, min(f) gives us the minimum operations needed across all possible ending values.

The time complexity is O(n) where n is the length of the array, and space complexity is O(1) due to the rolling array optimization.

Example Walkthrough

Let's trace through the algorithm with nums = [2, 1, 3, 2].

We maintain f[j] where f[0] represents min operations with last kept element = 1, f[1] for last kept = 2, and f[2] for last kept = 3.

Initial State: f = [0, 0, 0]

Processing element 2:

• Current element x = 2
• Calculate new state g:
  • g[0] (want last kept = 1, but current = 2): Must remove 2, so f[0] + 1 = 0 + 1 = 1
  • g[1] (want last kept = 2, current = 2): Can keep it! Take min(f[0], f[1]) = min(0, 0) = 0
  • g[2] (want last kept = 3, but current = 2): Must remove 2, so min(f[0], f[1], f[2]) + 1 = 0 + 1 = 1
• Update: f = [1, 0, 1]

Processing element 1:

• Current element x = 1
• Calculate new state g:
  • g[0] (want last kept = 1, current = 1): Can keep it! f[0] = 1
  • g[1] (want last kept = 2, but current = 1): Must remove 1, so min(f[0], f[1]) + 1 = min(1, 0) + 1 = 1
  • g[2] (want last kept = 3, but current = 1): Must remove 1, so min(f[0], f[1], f[2]) + 1 = min(1, 0, 1) + 1 = 1
• Update: f = [1, 1, 1]

Processing element 3:

• Current element x = 3
• Calculate new state g:
  • g[0] (want last kept = 1, but current = 3): Must remove 3, so f[0] + 1 = 1 + 1 = 2
  • g[1] (want last kept = 2, but current = 3): Must remove 3, so min(f[0], f[1]) + 1 = min(1, 1) + 1 = 2
  • g[2] (want last kept = 3, current = 3): Can keep it! min(f[0], f[1], f[2]) = min(1, 1, 1) = 1
• Update: f = [2, 2, 1]

Processing element 2:

• Current element x = 2
• Calculate new state g:
  • g[0] (want last kept = 1, but current = 2): Must remove 2, so f[0] + 1 = 2 + 1 = 3
  • g[1] (want last kept = 2, current = 2): Can keep it! min(f[0], f[1]) = min(2, 2) = 2
  • g[2] (want last kept = 3, but current = 2): Must remove 2, so min(f[0], f[1], f[2]) + 1 = min(2, 2, 1) + 1 = 2
• Update: f = [3, 2, 2]

Final Answer: min(f) = min(3, 2, 2) = 2

This means we need 2 operations (removals) minimum. Indeed, if we remove elements at indices 0 and 3 (the two 2's), we get [1, 3] which is non-decreasing.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the input array nums. The algorithm iterates through the array exactly once with a single for loop. Inside the loop, all operations (comparisons, assignments, and finding minimum values among at most 3 elements) are performed in constant time O(1). Therefore, the overall time complexity is O(n) * O(1) = O(n).

Space Complexity: O(1). The algorithm uses two fixed-size arrays f and g, each of size 3, regardless of the input size. These arrays store intermediate states for dynamic programming. Since the space used does not grow with the input size and remains constant at 6 integer values total, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding State Transitions

Pitfall: A common mistake is incorrectly calculating state transitions, particularly confusing when to add 1 (remove) versus when to keep the element. Developers often think dp[i] represents "keeping elements with value i+1" rather than "the last kept element has value i+1".

Example of Wrong Logic:

# WRONG: Thinking we need to remove when transitioning between different values
if current_num == 2:
    new_dp[0] = dp[0] + 1  # Wrong reason: thinking we remove because 2 != 1
    new_dp[1] = dp[1]      # Wrong: forgetting we can come from dp[0] too

Correct Understanding:

• new_dp[j] represents the minimum operations where the last kept element will be j+1
• When current_num doesn't match our target ending value j+1, we must remove it (+1 operation)
• When they match, we keep the element (no additional operation)

2. Incorrect Minimum Calculation for Previous States

Pitfall: Forgetting that when keeping an element with value k, all previous kept elements must be ≤ k to maintain non-decreasing order.

Wrong Implementation:

if current_num == 2:
    new_dp[1] = dp[1]  # WRONG: only considering previous state ending with 2

Correct Implementation:

if current_num == 2:
    new_dp[1] = min(dp[:2])  # CORRECT: can come from states ending with 1 or 2

3. Off-by-One Errors in Index Mapping

Pitfall: Confusing the mapping between dp indices and actual values. Remember that dp[0] corresponds to value 1, dp[1] to value 2, and dp[2] to value 3.

Solution: Always use clear variable names or comments to indicate the mapping:

# dp[0] -> last kept element is 1
# dp[1] -> last kept element is 2  
# dp[2] -> last kept element is 3

4. Not Handling Edge Cases

Pitfall: The code might fail if not properly initialized or if the input array is empty.

Robust Solution:

def minimumOperations(self, nums: List[int]) -> int:
    if not nums:  # Handle empty array
        return 0
  
    dp = [0] * 3
    # ... rest of the code

5. Space Optimization Confusion

Pitfall: When optimizing from 2D DP to 1D rolling array, developers might accidentally use the updated values instead of the previous iteration's values.

Prevention: Always create a new array for the current iteration:

for current_num in nums:
    new_dp = [0] * 3  # Create fresh array for current iteration
    # ... calculate new_dp based on dp ...
    dp = new_dp  # Update only after all calculations are done

Never modify dp in-place during calculations as it would corrupt the state transitions.