Minimum Replacements to Sort the Array

hard array math greedy

Problem

In one operation, replace any element with two positive integers that sum to it. Return the minimum number of operations needed to make nums non-decreasing.

Inputnums = [3, 9, 3]

Output2

Split 9 into [3, 3, 3]; total 2 replacements.

nums (positive ints, comma-separated)

def minimum_replacement(nums):
    ops = 0
    limit = nums[-1]
    for i in range(len(nums) - 2, -1, -1):
        if nums[i] > limit:
            parts = (nums[i] + limit - 1) // limit
            ops += parts - 1
            limit = nums[i] // parts
        else:
            limit = nums[i]
    return ops

function minimumReplacement(nums) {
  let ops = 0;
  let limit = nums[nums.length - 1];
  for (let i = nums.length - 2; i >= 0; i--) {
    if (nums[i] > limit) {
      const parts = Math.ceil(nums[i] / limit);
      ops += parts - 1;
      limit = Math.floor(nums[i] / parts);
    } else {
      limit = nums[i];
    }
  }
  return ops;
}

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

long long minimumReplacement(vector<int>& nums) {
    long long ops = 0;
    int limit = nums.back();
    for (int i = (int)nums.size() - 2; i >= 0; i--) {
        if (nums[i] > limit) {
            int parts = (nums[i] + limit - 1) / limit;
            ops += parts - 1;
            limit = nums[i] / parts;
        } else {
            limit = nums[i];
        }
    }
    return ops;
}

Explanation

We want the array to be non-decreasing, and our only tool is splitting a number into two positive pieces. The trick is to work from right to left, keeping a running limit = the largest value the current element is allowed to be.

The rightmost number never needs splitting, so it sets the first limit. Moving left, if nums[i] is already ≤ limit, it is fine and simply becomes the new limit.

If nums[i] > limit, we must break it into several pieces, each ≤ limit. The fewest pieces is parts = ceil(nums[i] / limit), which costs parts - 1 operations (one split makes two pieces, etc.).

To leave the most room for elements further left, we make the pieces as even as possible, so the smallest piece is floor(nums[i] / parts), and that becomes the new limit.

Example: [3, 9, 3]. Start limit = 3. At 9: parts = ceil(9/3) = 3, cost 2, new limit = floor(9/3) = 3. At the first 3 it fits, so total operations = 2.

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