Minimum Replacements to Sort the Array

Problem

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 innon-decreasing order.

Examples

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

Solution

Method 1 – Greedy Backward Splitting

Intuition

To make the array non-decreasing, we process from right to left. For each element, if it's greater than the next, split it into parts so all are ≤ next. The minimum number of splits is ceil(nums[i]/next) - 1.

Approach

1. Start from the end, set next = nums[-1].
2. For each nums[i] from n-2 to 0:
   • If nums[i] ≤ next, set next = nums[i].
   • Else, split nums[i] into parts ≤ next.
   • Count splits: parts = ceil(nums[i]/next), ops += parts-1, next = nums[i]//parts.

Code

C++

#include <vector>
#include <cmath>
class Solution {
public:
    long long minimumReplacement(std::vector<int>& nums) {
        int n = nums.size();
        long long ops = 0;
        int next = nums[n-1];
        for (int i = n-2; i >= 0; --i) {
            if (nums[i] <= next) next = nums[i];
            else {
                int parts = (nums[i]+next-1)/next;
                ops += parts-1;
                next = nums[i]/parts;
            }
        }
        return ops;
    }
};

Go

func minimumReplacement(nums []int) int64 {
    n := len(nums)
    ops := int64(0)
    next := nums[n-1]
    for i := n-2; i >= 0; i-- {
        if nums[i] <= next { next = nums[i] } else {
            parts := (nums[i]+next-1)/next
            ops += int64(parts-1)
            next = nums[i]/parts
        }
    }
    return ops
}

Java

class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length, next = nums[n-1];
        long ops = 0;
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= next) next = nums[i];
            else {
                int parts = (nums[i]+next-1)/next;
                ops += parts-1;
                next = nums[i]/parts;
            }
        }
        return ops;
    }
}

Kotlin

class Solution {
    fun minimumReplacement(nums: IntArray): Long {
        var next = nums.last(); var ops = 0L
        for (i in nums.size-2 downTo 0) {
            if (nums[i] <= next) next = nums[i]
            else {
                val parts = (nums[i]+next-1)/next
                ops += parts-1
                next = nums[i]/parts
            }
        }
        return ops
    }
}

Python

class Solution:
    def minimumReplacement(self, nums: list[int]) -> int:
        ops, next = 0, nums[-1]
        for i in range(len(nums)-2, -1, -1):
            if nums[i] <= next:
                next = nums[i]
            else:
                parts = (nums[i]+next-1)//next
                ops += parts-1
                next = nums[i]//parts
        return ops

Rust

impl Solution {
    pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
        let n = nums.len();
        let mut ops = 0i64;
        let mut next = nums[n-1];
        for i in (0..n-1).rev() {
            if nums[i] <= next { next = nums[i]; }
            else {
                let parts = (nums[i]+next-1)/next;
                ops += (parts-1) as i64;
                next = nums[i]/parts;
            }
        }
        ops
    }
}

TypeScript

class Solution {
    minimumReplacement(nums: number[]): number {
        let ops = 0, next = nums[nums.length-1];
        for (let i = nums.length-2; i >= 0; i--) {
            if (nums[i] <= next) next = nums[i];
            else {
                const parts = Math.floor((nums[i]+next-1)/next);
                ops += parts-1;
                next = Math.floor(nums[i]/parts);
            }
        }
        return ops;
    }
}

Complexity

• ⏰ Time complexity: O(n) — One pass from right to left.
• 🧺 Space complexity: O(1) — Only a few variables.