2366

2366. Minimum Replacements to Sort the Array (Hard)

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

• For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return the minimum number of operations to make an array that is sorted in non-decreasing order.

 

Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0. 

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Companies: Google, Expedia

Related Topics:
Array, Math, Greedy

Similar Questions:

• Minimum Operations to Make the Array Increasing (Easy)

Solution 1. Greedy

Intuition

If nums is not sorted, there exists at least one adjacent pair nums[i], nums[i + 1] where nums[i] > nums[i + 1]. How should we handle this pair of numbers that don't adhere to the sorted order? Should we break down the larger nums[i] using replacement operations or the smaller nums[i + 1]? To minimize the number of steps, it is unnecessary to break down the smaller number because it would only increase the number of replacement operations.

Now that we understand the logic for handling adjacent unsorted pairs, the next question is the order in which we process nums. Here, we need to traverse in reverse order. The reason is that our replacement operations will only make the current nums[i] become two (or more) smaller numbers.

If we start from the end and move toward the beginning, we can ensure that the suffix array always remains sorted. This is because we are replacing nums[i] with smaller elements, which will not disrupt the sorting structure of the suffix array (elements at indices i + 1, i + 2, etc. that are already sorted).

On the contrary, if we start from the beginning and replace a larger element with smaller elements, it may disrupt the sorted order of the previously processed elements on the left, and we'll end up needing more operations to sort the processed subarray again, as shown in the picture below.

Now that we know the traversal order, the next step is to minimize the number of operations. When we reach nums[i] during the reverse traversal, if nums[i] > nums[i + 1], how many smaller numbers should we break nums[i] into? Here are a few options:

• Breaking nums[i] into many 1s, which would require too many operations.
• Breaking nums[i] according to the value of nums[i + 1], with the remainder of nums[i] divided by nums[i + 1] becoming the new nums[i]. However, in some cases, this method can result in a very small nums[i]. For example, [7] will be replaced by [1, 3, 3], thus all the previous elements must be replaced by 1s.
• Any better method?

We can use a method similar to option 2:

• If nums[i] is divisible by nums[i + 1], we break nums[i] into multiple elements of value nums[i + 1].
• If nums[i] is not divisible by nums[i + 1], we break nums[i] into (nums[i] / nums[i + 1] + 1) sorted elements, with the largest element being nums[i + 1] and the smallest element being nums[i + 1] - 1. For example, if nums[i] = 7 and nums[i + 1] = 3, we replace [7] with [2, 2, 3] by two replacement operations.

The reason that [2, 2, 3] is a better split than [1, 3, 3] is that all future elements on the left will need to be less than or equal to the elements we split into here. Thus, we would prefer the larger 2 over the smaller 1, so we have more options for future splits.

In summary, we traverse nums in reverse and break down each nums[i] that violates the sorting order according to the approach mentioned above. We also accumulate the number of replacement operations. It is important to note that when we break nums[i] into n elements, it actually requires n - 1 steps.

Please refer to the picture below as a detailed example:

In the previous paragraph, we discussed two cases for calculating num_elements, which can be simplified by nums_elements = (nums[i] + nums[i + 1] - 1) / nums[i + 1]. Regardless of whether nums[i] is divisible as nums[i + 1] or not, we will always obtain the correct result.

Algorithm

1. Set answer as 0, and set n as the length of nums.

2. Iterate over nums backward from nums[n - 2], as we don't need to replace nums[n - 1].

   • If nums[i] <= nums[i + 1], move on to the next element nums[i - 1].
   • If nums[i] is divisible by nums[i + 1], break nums[i] into nums_elements = num[i] / nums[i + 1] elements, otherwise, break num[i] into nums_elements = nums[i] / nums[i + 1] + 1 elements. This requires num_elements - 1 replacement operations. Hence, we increment answer by num_elements - 1.
   • The largest possible nums[i] after the operations is nums[i] / num_elements, update nums[i] as nums[i] / num_elements.

3. Return answer once the iteration is complete.

Complexity Analysis

Let nnn be the size of nums.

• Time complexity: O(n)O(n)O(n)

  • We iterate over nums once in reverse.
  • At each step, we calculate num_elements, answer and nums[i], which takes O(1)O(1)O(1) time.

• Space complexity: O(1)O(1)O(1)

  • We're modifying nums in place and not using any additional data structures that scale with the size of the input.
  • Note that some interviewers might not want you to modify the input as it is not considered good practice in real-world coding. If that's the case, you could slightly modify the algorithm to use an integer to track the most recently split numbers.

// OJ: https://leetcode.com/problems/minimum-replacements-to-sort-the-array
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    long long minimumReplacement(vector<int>& A) {
        long long ans = 0, N = A.size();
        for (int i = N - 2; i >= 0; --i) {
            if (A[i] <= A[i + 1]) continue;
            long long cnt = (A[i] + A[i + 1] - 1LL) / A[i + 1];
            ans += cnt - 1;
            A[i] /= cnt;
        }
        return ans;
    }
};