2366. Minimum Replacements to Sort the Array
Description
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 replacenums[1]
with2
and4
and convertnums
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
Solutions
Solution 1: Greedy Approach
We observe that to make the array $nums$ non-decreasing or monotonically increasing, the elements towards the end of the array should be as large as possible. Therefore, it is unnecessary to replace the last element $nums[n-1]$ of the array $nums$ with multiple smaller numbers.
In other words, we can traverse the array $nums$ from the end to the beginning, maintaining the current maximum value $mx$, initially $mx = nums[n-1]$.
- If the current element $nums[i] \leq mx$, there is no need to replace $nums[i]$. We simply update $mx = nums[i]$.
- Otherwise, we need to replace $nums[i]$ with multiple numbers that sum to $nums[i]$. The maximum of these numbers is $mx$, and the total number of replacements is $k=\left \lceil \frac{nums[i]}{mx} \right \rceil$. Therefore, we need to perform $k-1$ operations, which are added to the answer. Among these $k$ numbers, the smallest number is $\left \lfloor \frac{nums[i]}{k} \right \rfloor$. Therefore, we update $mx = \left \lfloor \frac{nums[i]}{k} \right \rfloor$.
After the traversal, we return the total number of operations.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|