Minimum Replacements to Sort the Array — Problem & Solution
Minimum Replacements to Sort the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Minimum Replacements to Sort the Array is a hard coding problem on arrays, math and greedy, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Math, Greedy
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one operation you may replace any element with two positive integers that sum to it, inserted in its place.
Return the minimum number of operations that makes nums non-decreasing.
Example 1
Input: nums = [3,9,3]
Output: 2
Explanation: Split the 9 into `3,3,3`, giving `[3,3,3,3,3]` in two operations.
Example 2
Input: nums = [1,2,3,4,5]
Output: 0
Explanation: Already non-decreasing.
Example 3
Input: nums = [10,4]
Output: 2
Explanation: Split the 10 into `3,3,4`.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^5
Hints for Minimum Replacements to Sort the Array
Hint 1
Work right to left: the last element is fixed, and everything to its left must end no larger than the smallest piece to its right.
Hint 2
To split
vso every piece is at mostlimit, you needceil(v / limit)pieces — and that ispieces - 1operations.Hint 3
Splitting as evenly as possible maximises the smallest piece, which is
floor(v / pieces)— and that becomes the new limit.
How to solve Minimum Replacements to Sort the Array
Sweep right to left carrying limit, the largest value the current element's pieces may take. Splitting v into p = ceil(v / limit) pieces costs p - 1 operations, and the best achievable smallest piece is floor(v / p), which becomes the limit for the element to its left.
Approach
- Start with
limit = nums[n-1]andops = 0. - For
ifromn-2down to 0: setp = ceil(nums[i] / limit), addp - 1toops. - Update
limit = floor(nums[i] / p). - Return
ops.
Why it works
Two greedy facts carry it. First, ceil(v / limit) is the fewest pieces that can all fit under limit — fewer pieces would force one above it. Second, given that piece count, splitting as evenly as possible makes the smallest piece as large as it can be, and only the smallest piece constrains what comes further left. Sweeping left to right cannot work, because the pieces you choose depend on what follows.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The direction matters: the rightmost element is never split.
- The new limit is
floor(v / p), notlimit— an even split may leave headroom. - At the upstream bounds the answer exceeds a 32-bit integer; here the constraints keep it inside one.
Reference solution
Python
from typing import List
def minimumReplacement(nums: List[int]) -> int:
limit = nums[-1]
ops = 0
for i in range(len(nums) - 2, -1, -1):
parts = -(-nums[i] // limit)
ops += parts - 1
limit = nums[i] // parts
return opsJava
public static int minimumReplacement(int[] nums) {
int n = nums.length;
int limit = nums[n - 1];
int ops = 0;
for (int i = n - 2; i >= 0; i--) {
int parts = (nums[i] + limit - 1) / limit;
ops += parts - 1;
limit = nums[i] / parts;
}
return ops;
}C++
int minimumReplacement(vector<int>& nums) {
int n = (int) nums.size();
int limit = nums[n - 1];
int ops = 0;
for (int i = n - 2; i >= 0; i--) {
int parts = (nums[i] + limit - 1) / limit;
ops += parts - 1;
limit = nums[i] / parts;
}
return ops;
}JavaScript
var minimumReplacement = function(nums) {
var n = nums.length;
var limit = nums[n - 1], ops = 0;
for (var i = n - 2; i >= 0; i--) {
var parts = Math.ceil(nums[i] / limit);
ops += parts - 1;
limit = Math.floor(nums[i] / parts);
}
return ops;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms