Minimum Replacements to Sort the Array

Problem#

Replace any element with a sequence of two or more positive integers summing to it (one operation). Return the minimum operations to make the array non-decreasing.

Examples#

nums = [3,9,3] → 2 (split 9 into 3+3+3)
nums = [1,2,3,4,5] → 0

Hints#

Hint 1

Process right-to-left. The current “ceiling” is the maximum first-part of any future split. For nums[i] larger than ceiling, split into ceil(nums[i]/ceiling) parts, each as large as possible (so the first part is nums[i] / parts).

Approach#

Walk from right to left. Maintain ceiling = nums[n-1]. For each nums[i]: if nums[i] <= ceiling, set ceiling = nums[i]. Else split into parts = ceil(nums[i] / ceiling), costing parts - 1 ops; new ceiling = nums[i] / parts (floor — first part of an even split is the smallest).

Solution#

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long ops = 0;
        long long ceiling = nums.back();
        for (int i = (int)nums.size() - 2; i >= 0; --i) {
            if (nums[i] <= ceiling) {
                ceiling = nums[i];
            } else {
                long long parts = (nums[i] + ceiling - 1) / ceiling;  // ceil
                ops += parts - 1;
                ceiling = nums[i] / parts;                             // first part
            }
        }
        return ops;
    }
};

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

from typing import List

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

function minimumReplacement(nums) {
    let ops = 0n;
    let ceiling = BigInt(nums[nums.length - 1]);
    for (let i = nums.length - 2; i >= 0; i--) {
        const v = BigInt(nums[i]);
        if (v <= ceiling) {
            ceiling = v;
        } else {
            const parts = (v + ceiling - 1n) / ceiling;
            ops += parts - 1n;
            ceiling = v / parts;
        }
    }
    return Number(ops);
}

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

function minimumReplacement(nums: number[]): number {
    let ops = 0n;
    let ceiling = BigInt(nums[nums.length - 1]);
    for (let i = nums.length - 2; i >= 0; i--) {
        const v = BigInt(nums[i]);
        if (v <= ceiling) {
            ceiling = v;
        } else {
            const parts = (v + ceiling - 1n) / ceiling;
            ops += parts - 1n;
            ceiling = v / parts;
        }
    }
    return Number(ops);
}

Editorial#

The “first-part of an even split = nums[i] / parts” is the maximum starting value for the next position, which is what we want to relax the constraint for predecessors. Going right-to-left lets us treat the ceiling as the “max value we can leave here”.

Complexity#

Time: O(n).
Space: O(1).

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#