2826. Sorting Three Groups


Problem Description

The challenge presents us with a 0-indexed integer array nums of length n. In this scenario, there is an intriguing way numbers are grouped: each number from 0 to n - 1 is assigned to one of three possible groups (1, 2, or 3) based on the value of nums[i], meaning the index of the number indicates which number we're referring to, and the value at that index tells us the group to which it belongs. It's important to note that some groups might not have any numbers assigned to them—they can be empty.

The task is to transform nums into a "beautiful array". For an array to be considered beautiful, the numbers must be sorted in non-decreasing order across all groups when reconvened into a single array. This can be achieved through a series of operations where we may choose any number x (index) and change its group by setting nums[x] to 1, 2, or 3.

The processes used to make a "beautiful array" are as such:

  • First, the numbers in each individual group are sorted.
  • Then, the numbers from groups 1, 2, and 3 are appended to form a new array res in that specific group order.

The challenge posed to us is to determine the minimum number of such operations necessary to change the original nums array into a beautiful array.

Intuition

Creating a beautiful array is essentially similar to sorting, but with an unique constraint: we have to sort numbers into three buckets or groups before concatenating them. However, we can only move numbers between these groups, not arbitrarily reorder them within a group.

Given this constraint, we recognize the problem as one of dynamic programming (DP), because the optimal solution to make a portion of the array beautiful can help inform the next step. What we're effectively doing in the DP approach is keeping track of the cost of sorting each prefix of the array nums up to index i, while considering that each element nums[i] can belong to any of the three groups. The state, therefore, involves the minimum cost of operations (the number of group changes) required to achieve a sorted array up to that point. This cost depends on the last group in which we've placed nums[i], as that determines where we can put nums[i + 1] without increasing the number of moves.

In the solution code provided, f represents an array that maintains this cost for each of the three groups. For each number in nums, we create a new array g that temporarily stores the updated costs after considering the current number's possible group placements. If the current number is 1, we must place it in group 1 without any operation, hence g[0] just carries over the existing cost in f[0]. For the number to be in group 2, it would require an operation if the last number was in group 1, but not if it was already in group 2, thereby determining the cost as min(f[:2]) + 1. Similar logic is applied for when the number is 2 and when it is 3. Each possible number placement is examined, and the costs are updated accordingly.

After considering all the numbers in nums, the minimum value in f reflects the smallest number of operations required to achieve a beautiful array.

Learn more about Dynamic Programming patterns.

Solution Approach

The provided Python solution implements a dynamic programming (DP) strategy to minimize the number of operations required for creating a beautiful array. Here's a step-by-step breakdown of the implementation:

  1. Initialization: A list f is used to keep track of the minimum number of operations necessary to reach a state where the last group (either 1, 2, or 3) has been populated. Initially, f is set to [0, 0, 0], assuming no operations are performed yet.

  2. Iterating Over the Array: The solution iterates over each element x of nums. A temporary list g is created to store the new costs calculated based on the current number and prior costs.

  3. Evaluating Placement Options: Depending on the value of x (which corresponds to the current group the number is in), there are different implications for the number of operations needed.

    • If x is 1, it means the current number is already in group 1, which is the correct placement (no extra operation needed for this group). So, we copy the previous cost for group 1 to g[0].
    • To keep the array sorted (beautiful), the number can be placed in group 2 only if it follows a number that was in group 1 or already in group 2 (hence g[1] is the minimum of the previous costs for groups 1 and 2 plus one possible operation).
    • To place a number in group 3, it may follow any of the three previous group placements (so g[2] is assigned as the minimum of all previous costs incremented by one for the operation).
  4. Handling Different Values of x: The process slightly varies when x is 2 or 3, as the cost of 'leaving the number where it is' applies only to the group x is currently in and needs an increment for the other groups.

  5. Updating State: After considering all placement options for the current number, we update f to the new costs stored in g. This continues for the entire array.

  6. Extracting Result: Once we have processed all numbers in nums, the minimum number in f gives us the minimum operations required to make the entire array beautiful. At this point, each element of f represents the cost of the operations performed up to the last number in nums, assuming the last number is in group 1, 2, or 3, respectively.

This solution emphasizes the importance of maintaining a historical context for costs (DP) and understanding that only the 'state transitions' (change of groups) incur a cost, not the internal ordering within the groups.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement priority queue?

Example Walkthrough

Let's illustrate the solution approach with a small example where we have an integer array nums of length n = 5, and the content of nums is [2, 1, 2, 3, 1]. We need to determine the minimum number of operations to transform nums into a beautiful array.

  1. Initialization: We start with an array f = [0, 0, 0] to keep track of the minimum operations needed for the three possible group placements of the last number.

  2. Iterating Over the Array:

  • For the first element, x = nums[0] = 2, we need f to reflect the cost after considering this element. The temporary array g is initialized.
  1. Evaluating Placement Options:
  • Since x is 2, we can consider placing it in group 2 with no cost (g[1] = f[1]). But if we want to place it in group 1 or 3, since it's not naturally there, it requires one operation (g[0] = f[0] + 1 for group 1, and g[2] = f[2] + 1 for group 3). So, g becomes [1, 0, 1].
  1. Updating State:
  • We update f to be the same as g, so f now becomes [1, 0, 1].
  1. Continuing with Array:
  • The next element, x = nums[1] = 1, naturally belongs to group 1, so g[0] = f[0]. For group 2 it could either stay as it is or follow an element in group 1, so g[1] = min(f[0], f[1]) + 1. And for group 3, it can follow any of the previous groups, so g[2] = min(f) + 1. The updated g becomes [1, 1, 1].
  • Repeat this process for each element in the array, updating the state f with g after each iteration:

Element = 2: g recalculated to [2, 1, 1] Element = 3: g recalculated to [2, 2, 1] Element = 1: g recalculated to [2, 2, 2]

  1. Extracting Result:
  • After processing all elements in nums, the final values of f is [2, 2, 2]. The minimum number of operations required to make nums a beautiful array is the minimum of these values, which is 2.

In conclusion, given the array [2, 1, 2, 3, 1], we find that at least 2 operations are required to transform it into a beautiful array where each group is sorted, and then concatenated together in group order.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumOperations(self, nums: List[int]) -> int:
5        # f will hold the minimum operations required to adjust the list
6        # to the constraints of having 1s, 2s and no elements in position i
7        min_operations = [0] * 3
8
9        # Loop through each element in the nums list
10        for number in nums:
11            # g will temporarily hold the new calculated minimum operations
12            new_min_operations = [0] * 3
13
14            # If the current number is 1
15            if number == 1:
16                new_min_operations[0] = min_operations[0]  # No change needed
17                new_min_operations[1] = min(min_operations[:2]) + 1  # Increment operations for 1s or 2s
18                new_min_operations[2] = min(min_operations) + 1  # Increment as 1 is not allowed here
19            # If the current number is 2
20            elif number == 2:
21                new_min_operations[0] = min_operations[0] + 1  # Increment as 2 is not allowed here
22                new_min_operations[1] = min(min_operations[:2])  # No change needed
23                new_min_operations[2] = min(min_operations) + 1  # Increment operations for no number
24            # If the current number is neither 1 nor 2
25            else:
26                new_min_operations[0] = min_operations[0] + 1  # Increment as number is not allowed here
27                new_min_operations[1] = min(min_operations[:2]) + 1  # Increment operations for 1s or 2s
28                new_min_operations[2] = min(min_operations)  # No change needed 
29
30            # Update min_operations with the new calculated minimum operations
31            min_operations = new_min_operations
32
33        # Return the minimum of the calculated operations
34        return min(min_operations)
35
1class Solution {
2    public int minimumOperations(List<Integer> nums) {
3        // Initialize an array to keep track of the minimum operations
4        int[] minOps = new int[3];
5      
6        // Loop through each number in the input list
7        for (int num : nums) {
8            // Create a temporary array to store the current state of minimum operations
9            int[] currentOps = new int[3];
10          
11            // Check the current number and update the temporary state array accordingly
12            if (num == 1) {
13                // If the current number is 1, we don't change the first state
14                currentOps[0] = minOps[0];
15                // We can reach the second state from the first or second state with one operation
16                currentOps[1] = Math.min(minOps[0], minOps[1]) + 1;
17                // We can reach the third state from any state with one operation
18                currentOps[2] = Math.min(Math.min(minOps[0], minOps[1]), minOps[2]) + 1;
19            } else if (num == 2) {
20                // If the current number is 2, we can reach the first state with one operation
21                currentOps[0] = minOps[0] + 1;
22                // We can reach the second state from the first or second state with no operation
23                currentOps[1] = Math.min(minOps[0], minOps[1]);
24                // We can reach the third state from any state with one operation
25                currentOps[2] = Math.min(Math.min(minOps[0], minOps[1]), minOps[2]) + 1;
26            } else {
27                // If the current number is neither 1 nor 2, we can reach the first state with one operation
28                currentOps[0] = minOps[0] + 1;
29                // We can reach the second state from the first or second state with one operation
30                currentOps[1] = Math.min(minOps[0], minOps[1]) + 1;
31                // We can reach the third state from any state with no additional operation
32                currentOps[2] = Math.min(Math.min(minOps[0], minOps[1]), minOps[2]);
33            }
34          
35            // Update our tracking array to the current state
36            minOps = currentOps;
37        }
38      
39        // Calculate and return the minimum number of operations among all three states
40        return Math.min(Math.min(minOps[0], minOps[1]), minOps[2]);
41    }
42}
43
1class Solution {
2public:
3    int minimumOperations(vector<int>& nums) {
4        // The vector 'minimumOps' stores the minimum operations needed to
5        // convert the sequence up to the current point, based on the last number in the sequence.
6        // minimumOps[0]: no operations performed, still at first number
7        // minimumOps[1]: one operation performed, at second number
8        // minimumOps[2]: two operations performed, at third number
9        vector<int> minimumOps(3, 0);
10
11        for (int num : nums) {
12            // 'nextOps' stores the number of operations needed for the current state.
13            vector<int> nextOps(3, 0);
14
15            if (num == 1) {
16                // If current number is 1, keep the same state or increment operations.
17                nextOps[0] = minimumOps[0]; // Previous number was also 1, no change in operations.
18                nextOps[1] = min(minimumOps[0], minimumOps[1]) + 1; // Move from 1st number or stay at 2nd number, with additional operation.
19                nextOps[2] = min({minimumOps[0], minimumOps[1], minimumOps[2]}) + 1; // Move to 3rd number from any state.
20            } else if (num == 2) {
21                // If current number is 2, we need to perform one more operation if at first number, or we can stay at second number.
22                nextOps[0] = minimumOps[0] + 1; // Add one operation to move from 1st number.
23                nextOps[1] = min(minimumOps[0], minimumOps[1]); // Keep the minimum operations from 1st or 2nd number.
24                nextOps[2] = min(minimumOps[0], min(minimumOps[1], minimumOps[2])) + 1; // Move to 3rd number from any state with an additional operation.
25            } else {
26                // If current number is neither 1 nor 2, just increment operations needed as one operation is needed to change this number to either 1 or 2.
27                nextOps[0] = minimumOps[0] + 1; // Add one operation to move away from 1st number.
28                nextOps[1] = min(minimumOps[0], minimumOps[1]) + 1; // Add operation to keep it second number or move from first to second number.
29                nextOps[2] = min(minimumOps[0], min(minimumOps[1], minimumOps[2])); // Stay at third number as it is the most different.
30            }
31
32            // Update 'minimumOps' with the new calculated operations 'nextOps'.
33            minimumOps = move(nextOps);
34        }
35
36        // Return the minimum of all the calculated operations to make the sequence of either 1s or 2s.
37        return min({minimumOps[0], minimumOps[1], minimumOps[2]});
38    }
39};
40
1function minimumOperations(nums: number[]): number {
2    // Initialize an array to store the frequencies of operations required to reach states 0, 1, 2.
3    let operationsFrequencies: number[] = new Array(3).fill(0);
4
5    // Iterate over each number in the input array.
6    for (const num of nums) {
7        // Initialize an array to store the new frequencies of operations after considering the current number.
8        const newFrequencies: number[] = new Array(3).fill(0);
9
10        // Check the value of the current number to decide the operations needed.
11        if (num === 1) {
12            // If the number is 1, the operations required to reach each state are updated.
13            newFrequencies[0] = operationsFrequencies[0];
14            newFrequencies[1] = Math.min(operationsFrequencies[0], operationsFrequencies[1]) + 1;
15            newFrequencies[2] = Math.min(operationsFrequencies[0], Math.min(operationsFrequencies[1], operationsFrequencies[2])) + 1;
16        } else if (num === 2) {
17            // If the number is 2, similar calculations are done for each state.
18            newFrequencies[0] = operationsFrequencies[0] + 1;
19            newFrequencies[1] = Math.min(operationsFrequencies[0], operationsFrequencies[1]);
20            newFrequencies[2] = Math.min(operationsFrequencies[0], Math.min(operationsFrequencies[1], operationsFrequencies[2])) + 1;
21        } else {
22            // For a number that's neither 1 nor 2, again the states are updated accordingly.
23            newFrequencies[0] = operationsFrequencies[0] + 1;
24            newFrequencies[1] = Math.min(operationsFrequencies[0], operationsFrequencies[1]) + 1;
25            newFrequencies[2] = Math.min(operationsFrequencies[0], Math.min(operationsFrequencies[1], operationsFrequencies[2]));
26        }
27        // The current frequencies are updated to be the new frequencies calculated for this iteration.
28        operationsFrequencies = newFrequencies;
29    }
30    // The function returns the minimum number of operations to be in any of the states for the entire array.
31    return Math.min(...operationsFrequencies);
32}
33

Time and Space Complexity

The code snippet provided is a dynamic programming solution that aims to find the minimum number of operations required to reduce an array of numbers to a certain condition. The array f represents the state at the previous step, and array g represents the state at the current step.

Time Complexity

The time complexity of the code is determined primarily by the for-loop that iterates over each element in the nums array. Inside this loop, a fixed number of operations are performed. Specifically, the loop executes once for each of the n elements of nums, and within the loop, a constant number of assignments and minimum function calls are performed. Each minimum function call operates over an array of fixed size 3 (or 2 in the case of min(f[:2])), which is a constant time operation.

Thus, the time complexity is O(n), where n is the length of the nums array.

Space Complexity

The space complexity of the algorithm is determined by the space required to store the f and g arrays, and any additional variables used for iteration and temporary storage. Since f and g are arrays of constant size 3, they do not scale with the input size n.

Hence, the space complexity is O(1), as the space used does not increase with the size of the input.

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


Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄