Minimum Replacements to Sort the Array
HardPrompt
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]with2and4and convertnumsto[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 <= 1051 <= nums[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
A less optimal greedy approach is to iterate through the array from right to left. When an element nums[i] is found to be greater than the element to its right (next_val), we must split nums[i]. A simple, but naive, way to split nums[i] is to break it down into pieces that are mostly of size next_val. This strategy, while seemingly logical, makes a poor choice for the new constraint on the next element, leading to a suboptimal total number of operations.
Algorithm
- Initialize
operations = 0andnext_val = nums[n-1]. - Iterate from
i = n-2down to0. - If
nums[i] <= next_val, the array is locally sorted. Updatenext_val = nums[i]and continue. - If
nums[i] > next_val, a split is necessary. - Calculate operations needed for a naive split:
ops_needed = (nums[i] - 1) / next_val. Add this tooperations. - Update
next_valfor the next iteration. The newnext_valisnums[i] % next_val. If the remainder is 0, it'snext_valitself. - Return total
operations.
Walkthrough
This approach processes the array from right to left, ensuring that each element is less than or equal to the element that follows it. When nums[i] > next_val, where next_val is the value of the subsequent element (or the first part of it if it was split), nums[i] must be broken down.
The naive splitting strategy is as follows: break nums[i] into q = floor(nums[i] / next_val) pieces of size next_val, and one remainder piece r = nums[i] % next_val. For example, if nums[i] = 19 and next_val = 8, we split 19 into 3, 8, 8. This requires q=2 operations. The new constraint for nums[i-1] becomes the smallest piece of this split, which is r=3 (or next_val if r=0).
This choice is suboptimal because making the new constraint (next_val) as small as nums[i] % next_val can cause a cascade of additional, unnecessary splits for elements to the left.
class Solution { public long minimumReplacement(int[] nums) { int n = nums.length; long operations = 0; long next_val = nums[n - 1]; for (int i = n - 2; i >= 0; i--) { if (nums[i] <= next_val) { next_val = nums[i]; continue; } long current_val = nums[i]; // This calculation finds the number of operations based on this naive split. // It's equivalent to floor(current_val / next_val) if there's a remainder, // and floor(current_val / next_val) - 1 if there's no remainder. long num_ops = (current_val - 1) / next_val; operations += num_ops; // The new constraint for the left element is the remainder of the division. long remainder = current_val % next_val; next_val = (remainder == 0) ? next_val : remainder; } return operations; }}Complexity
Time
O(N), where N is the number of elements in the array. We perform a single pass through the array.
Space
O(1), as we only use a few variables to store the running count of operations and the next value constraint.
Trade-offs
Pros
The approach is simple to understand.
It correctly identifies the necessary condition for splitting.
It has an efficient time and space complexity.
Cons
This greedy strategy is not optimal. It does not guarantee the minimum number of replacements because its choice of the next constraint (
next_val) is too strict, potentially increasing future operations.
The most efficient and correct approach is a greedy algorithm that processes the array from right to left. By doing so, any decision to split an element nums[i] only depends on the element to its right, nums[i+1] (or its resulting pieces), and does not affect the already processed suffix of the array. The key is to make a locally optimal choice that is also globally optimal. This involves minimizing the number of splits for the current element while maximizing the value of the first resulting piece to relax the constraint for the next element.
Algorithm
- Initialize
operations = 0andnext_val = nums[n-1]. - Iterate from
i = n-2down to0. - If
nums[i] <= next_val, updatenext_val = nums[i]and proceed to the next element. - If
nums[i] > next_val, we must perform replacements: a. Calculate the minimum number of pieceskto splitnums[i]into, such that each piece is<= next_val. This isk = ceil(nums[i] / next_val), which can be calculated using integer arithmetic as(nums[i] + next_val - 1) / next_val. b. Addk - 1tooperations, as splitting intokpieces takesk - 1operations. c. Updatenext_valfor the next element on the left. To be least restrictive, we want the first piece of the split to be as large as possible. This is achieved by making the pieces as equal as possible. The newnext_valwill befloor(nums[i] / k). - After the loop, return the total
operations.
Walkthrough
We traverse the array from the second-to-last element to the first. We maintain a variable, next_val, which holds the value that the current element nums[i] must be less than or equal to. Initially, next_val is nums[n-1].
For each element nums[i], we check if nums[i] <= next_val.
- If it is, no operation is needed for this element. We update
next_valtonums[i]because the element to the left,nums[i-1], must now be less than or equal to the new, smaller valuenums[i]. - If
nums[i] > next_val, we must splitnums[i]into smaller pieces. To minimize operations, we must split it into the minimum number of pieces,k. Each piece must be at mostnext_val. The minimumkisceil(nums[i] / next_val). This split requiresk-1operations.
After splitting nums[i] into k pieces, the new constraint for nums[i-1] is the value of the first (and smallest) piece of the split. To give nums[i-1] the most 'room' and potentially avoid splitting it, we want this first piece to be as large as possible. This is achieved by making the k pieces as equal as possible. The smallest piece in such a distribution is floor(nums[i] / k). This becomes our new next_val.
This greedy choice is optimal because at each step we (1) perform the minimum operations required for the current element and (2) create the least restrictive condition for the subsequent elements.
class Solution { public long minimumReplacement(int[] nums) { int n = nums.length; long operations = 0; // The value that the current element must be less than or equal to. long next_val = nums[n - 1]; // We iterate from right to left. for (int i = n - 2; i >= 0; i--) { // If the current element is already in order, no operations needed. // Update next_val for the element to the left. if (nums[i] <= next_val) { next_val = nums[i]; continue; } // If the current element is larger, we must split it. long current_val = nums[i]; // Calculate how many pieces we need to split current_val into. // Each piece must be <= next_val. // k = ceil(current_val / next_val) long k = (current_val + next_val - 1) / next_val; // Splitting into k pieces requires k-1 operations. operations += k - 1; // The new constraint for the element to the left is the smallest possible // first piece, which we maximize by distributing current_val as evenly as possible. // new_next_val = floor(current_val / k) next_val = current_val / k; } return operations; }}Complexity
Time
O(N), where N is the number of elements in `nums`. The algorithm involves a single pass over the array from right to left.
Space
O(1). The algorithm uses only a few variables to keep track of the state (`operations`, `next_val`), regardless of the input size.
Trade-offs
Pros
This approach is guaranteed to find the minimum number of replacements.
It is highly efficient, with linear time complexity and constant space complexity.
Cons
The logic for calculating the number of pieces and the next constraint is slightly more involved than a naive approach, but it's essential for correctness.
Solutions
Solution
class Solution {public long minimumReplacement(int[] nums) { long ans = 0; int n = nums.length; int mx = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { if (nums[i] <= mx) { mx = nums[i]; continue; } int k = (nums[i] + mx - 1) / mx; ans += k - 1; mx = nums[i] / k; } return ans; }}class Solution {public: long long minimumReplacement(vector<int> &nums) { long long ans = 0; int n = nums.size(); int mx = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { if (nums[i] <= mx) { mx = nums[i]; continue; } int k = (nums[i] + mx - 1) / mx; ans += k - 1; mx = nums[i] / k; } return ans; }};class Solution: def minimumReplacement(self, nums: List[int]) -> int: ans = 0 n = len(nums) mx = nums[- 1] for i in range(n - 2, - 1, - 1): if nums[i] <= mx: mx = nums[i] continue k = (nums[i] + mx - 1) // mx ans += k - 1 mx = nums[i] // k return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.