Minimum Replacements to Sort the Array — Hard Problem & Solution

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 <= 1000
• 1 <= nums[i] <= 10^5

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

1. Start with limit = nums[n-1] and ops = 0.
2. For i from n-2 down to 0: set p = ceil(nums[i] / limit), add p - 1 to ops.
3. Update limit = floor(nums[i] / p).
4. 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), not limit — 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard