2366. Minimum Replacements to Sort the Array


Problem Description

You are provided with an array of integers called nums. The goal is to sort this array into non-decreasing order (where each number is less than or equal to the next) by performing a specific operation as many times as needed. The operation you can perform involves replacing a single element in the array with any two elements that sum up to the original element.

For instance, if you have an element 6 in the array, you can replace it with two elements 2 and 4 since 2 + 4 = 6. The challenge lies in figuring out the minimum number of such operations required to sort the entire array.

Intuition

The solution to this problem hinges on a key observation: replacing any number with two smaller numbers can potentially make sorting the array harder, as it introduces more elements that need to be in non-decreasing order. Therefore, we should aim to perform each replacement in a way that either maintains the current order or requires the least amount of subsequent operations.

To minimize operations, we work our way from the end of the array (the largest elements in a sorted array) to the beginning, adjusting each element so that it's not larger than the one already considered and positioned at the end.

As we move backwards:

  1. We want the current element to be less than or equal to the element after it (since the array must be in non-decreasing order).
  2. If the current element is already less than or equal to the next element, no operation is needed, and we move to the previous element.
  3. If the current element is larger, we need to split it into smaller numbers in a way that requires the minimum number of splits while ensuring that each new number is not larger than the next element.

The algorithm keeps track of the maximum allowed value (mx) for each replacement, which initially is the value of the last element. It computes the minimum number of splits (k) needed for the current element to satisfy the non-decreasing order constraint, and updates the answer (ans) with the number of operations needed (which is k - 1, since replacing one number with two requires one operation). After this, it updates the maximum allowed value for the next element accordingly.

The process continues until we've considered all elements of the array, and the minimum number of operations required to achieve a non-decreasing array is returned.

Learn more about Greedy and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Solution Approach

To implement the solution, we follow a reverse iteration. We initiate by setting the variable mx to the value of the last element in the array since we aim to ensure that all preceding numbers are less than or equal to this value.

The main logic resides in a for-loop that starts from the second-to-last element and moves towards the first element (index 0). Here's a breakdown:

  1. For-loop iteration: The loop starts at index n - 2 because we're comparing each element with the one after it. We decrement our index with every iteration, essentially moving from the end of the array to the start.

  2. Conditional Operation: For each number, we check if it's less than or equal to mx. If it is, we're already maintaining the non-decreasing order, so we set mx to the current number (since this can be the new maximum for the upcoming previous elements) and continue to the next iteration without any further action.

    1if nums[i] <= mx:
    2    mx = nums[i]
    3    continue
  3. Calculation of Splits (k): When the current number is greater than mx, we calculate k, the minimum number of parts we need to split the current number into. This must be done such that each part does not exceed the value of mx. The calculation of k is given by (nums[i] + mx - 1) // mx. We add mx - 1 before integer division to ensure that all parts will be as large as possible without exceeding mx.

  4. Updating Answer: The number of new elements added (which is equal to the number of operations performed) will be k - 1. This value is added to ans, the variable tallying the minimum number of operations.

    1ans += k - 1
  5. Updating mx for the next iteration: We update mx to the largest possible value that a part can take after the split, which is nums[i] // k. This new value of mx will now act as the upper limit for the next (actually the previous since we're iterating in reverse) number in the array.

  6. Returning the result: Once the loop has been completed, the variable ans will hold the minimum number of operations needed to sort the array, which is returned as the result.

The algorithm does not require any additional data structures; it operates in-place, using only a few additional variables for keeping track of the state (ans, mx, k). It's a simple, yet efficient solution with a time complexity of O(n) as it requires a single iteration through the array.

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

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we are given the following array nums:

1nums = [10, 5, 13]

We need to sort this array into non-decreasing order by replacing elements into sums as needed. Let's walk through the procedure step by step.

  1. We start by setting mx to the value of the last element in nums, which is 13. This is the maximum allowed value for its preceding elements.

  2. We then begin iterating from the second-to-last element, which is 5 at index 1.

    • For nums[1] which is 5, since 5mx (13), we do not need to perform any operations. We set mx to 5 (since 5 now becomes the maximum allowed value for the preceding element) and continue.
  3. Next, we check nums[0], which is 10. Since 10 > mx (5 now), we need to perform operations. Calculating k gives us:

    1k = (nums[0] + mx - 1) // mx = (10 + 5 - 1) // 5 = 2

    Since k is 2, it means we need to split 10 into two parts, each not exceeding 5 (the current mx). We can split it into [5, 5]. The number of new elements added is k - 1 which is 1. Thus, we have 1 operation performed.

  4. We update ans with the number of operations performed, so ans becomes 1.

  5. We update mx to the largest value possible after the splits, which is nums[0] // k = 10 // 2 = 5.

  6. Having iterated over all elements, we conclude that we needed a minimum of 1 operation to sort the array into non-decreasing order. So the answer (ans) is 1.

This is the result of using the approach described in the solution. The process is time-efficient as it iterates through the array just once, making the complexity O(n).

Solution Implementation

1class Solution:
2    def minimumReplacement(self, nums: List[int]) -> int:
3        # Initialize the count of replacements to 0.
4        replacement_count = 0
5      
6        # Get the number of elements in the nums list.
7        num_elements = len(nums)
8      
9        # Set the current maximum to the last element in the nums list.
10        # This maximum represents the highest number we can decrease to without making any replacements.
11        current_max = nums[-1]
12      
13        # Iterate through the list in reverse order, starting from the second to last element.
14        for i in range(num_elements - 2, -1, -1):
15            # If the current element is less than or equal to the current maximum,
16            # no replacements are needed. Update the current maximum to this element.
17            if nums[i] <= current_max:
18                current_max = nums[i]
19            else:
20                # If the current element is greater than the current maximum,
21                # we calculate the minimum number of replacements required.
22                # This is done by dividing the current element by the current maximum,
23                # and rounding up to ensure we get a value no larger than the current max.
24                # Then compute how many replacements are needed to reach this value.
25                replacements_needed = (nums[i] + current_max - 1) // current_max
26                replacement_count += replacements_needed - 1   # Increase the count of replacements
27              
28                # Update the current maximum to the value obtained by evenly dividing
29                # the current element by the number of replacements needed.
30                # This will be the new threshold for further calculations on previous elements.
31                current_max = nums[i] // replacements_needed
32      
33        # Return the total count of replacements required to make the array non-increasing.
34        return replacement_count
35
1class Solution {
2
3    // Method to find the minimum number of replacements to make the array non-increasing.
4    public long minimumReplacement(int[] nums) {
5        // Initialize the answer to accumulate the number of replacements.
6        long replacements = 0;
7        // Get the number of elements in the array.
8        int n = nums.length;
9        // Initialize the max value to the last element in the array (it's already in correct position).
10        int maxValue = nums[n - 1];
11
12        // Loop through the array from second-to-last to the first element.
13        for (int i = n - 2; i >= 0; --i) {
14            // If the current element is less than or equal to the max value,
15            // it is already in right position, thus move to the previous element.
16            if (nums[i] <= maxValue) {
17                maxValue = nums[i]; // Update the max value to the current element.
18                continue;
19            }
20
21            // If the current element is larger than the max value, calculate the number of parts
22            // this element needs to be split into to maintain non-increasing order.
23            int parts = (nums[i] + maxValue - 1) / maxValue;
24            // Update the replacements count by adding the number of new elements added
25            // (parts - 1 means how many splits we do, which equals to additional numbers introduced).
26            replacements += parts - 1;
27            // The new max value should be the average of the current element
28            // after replacing it with 'parts' equal or almost equal numbers.
29            maxValue = nums[i] / parts;
30        }
31
32        // Return the total number of replacements done to make the array non-increasing.
33        return replacements;
34    }
35}
36
1#include <vector>
2
3class Solution {
4public:
5    long long minimumReplacement(std::vector<int>& nums) {
6        long long operations = 0; // Stores the total number of operations required
7        int size = nums.size(); // Size of the input vector
8        int maxElement = nums[size - 1]; // Initialize maxElement with the last item in the vector
9
10        // Iterate from the second to last element to the beginning
11        for (int i = size - 2; i >= 0; --i) {
12            // If the current element is less than or equal to maxElement,
13            // it's already in the correct order, update maxElement if necessary
14            if (nums[i] <= maxElement) {
15                maxElement = nums[i];
16                continue;
17            }
18
19            // Calculate the minimum number of replacements needed for nums[i]
20            // such that each replaced number is less than or equal to maxElement
21            int replacements = (nums[i] + maxElement - 1) / maxElement;
22          
23            // The actual replacements will be one less than the calculated
24            // replacements since we are also including the current element
25            operations += replacements - 1;
26
27            // Update maxElement to the value of the largest possible replaced number
28            maxElement = nums[i] / replacements;
29        }
30      
31        // Return the total number of operations required to make the array 
32        // non-decreasing by replacing some numbers with multiple numbers.
33        return operations;
34    }
35};
36
1/**
2 * Calculates the minimum number of replacements needed such that for every i, 
3 * nums[i] is greater than or equal to nums[i + 1].
4 * 
5 * @param {number[]} nums - Array of numbers to be modified.
6 * @return {number} - The minimum number of replacements needed.
7 */
8function minimumReplacement(nums: number[]): number {
9    // Get the length of the array
10    const length = nums.length;
11  
12    // Initialize variable to store the current lowest number from the back
13    let currentMin = nums[length - 1];
14  
15    // Initialize variable to store the answer
16    let replacements = 0;
17
18    // Iterate from the second-to-last element down to the first element
19    for (let i = length - 2; i >= 0; --i) {
20        // If the current element is less than or equal to the current lowest number, no need to replace
21        if (nums[i] <= currentMin) {
22            currentMin = nums[i];
23            continue;
24        }
25        // Calculate how many times the current number needs to be divided
26        // to be less than or equal to the current lowest number.
27        const factor = Math.ceil(nums[i] / currentMin);
28      
29        // Accumulate the total number of replacements needed
30        replacements += factor - 1;
31      
32        // Update the current lowest number to be the divided number
33        currentMin = Math.floor(nums[i] / factor);
34    }
35  
36    // Return the total number of replacements
37    return replacements;
38}
39
Not Sure What to Study? Take the 2-min Quiz:

How many ways can you arrange the three letters A, B and C?

Time and Space Complexity

Time Complexity

The time complexity of the code provided is O(n) where n is the length of the input list nums. This is because the algorithm iterates through the list once in reverse, beginning from the penultimate element to the first element. The operations within each iteration of the loop take constant time, such as comparison, arithmetic operations, and variable assignments. There are no nested loops or additional function calls that would change the linearity of the time complexity.

Space Complexity

The space complexity of the code provided is O(1). The algorithm uses a fixed amount of extra space regardless of the input size. Only a few single-value variables (ans, n, mx) are used for storage, and their space does not scale with the size of the input nums. No additional data structures that would grow with the size of the input are used, so the space usage remains constant.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these properties could exist for a graph but not a tree?


Recommended Readings


Got a question? Ask the Teaching 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.


TA 👨‍🏫