{x}
blog image

Minimum Replacements to Sort the Array

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 in non-decreasing order.

 

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 <= 105
  • 1 <= nums[i] <= 109

Minimum Replacements to Sort the Array

This problem asks for the minimum number of operations to sort an array in non-decreasing order, where an operation involves replacing an element with two elements that sum to it. The key insight is a greedy approach: we process the array from right to left, aiming to keep the current maximum value as large as possible to minimize the number of replacements.

Approach

The algorithm iterates through the array from right to left. For each element:

  1. Check if it's already in order: If the current element is less than or equal to the current maximum (mx), it's already in order; we update mx to the current element and continue.

  2. Replace if needed: If the current element is greater than mx, we need to replace it. We determine the minimum number of replacements (k) needed by dividing the current element by mx and rounding up (using ceiling division). Each replacement adds k-1 to the total operations. The new mx becomes the floor of the current element divided by k. This ensures the new elements are as large as possible while still maintaining a non-decreasing sequence.

  3. Update the maximum: After processing, the mx is updated to the largest value encountered after a potential replacement, ensuring the next elements are compared to the largest possible value from the right part of the processed array.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the array. We iterate through the array once. The arithmetic operations within the loop are constant time.
  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        ans = 0
        n = len(nums)
        mx = nums[-1]  # Initialize mx to the last element
        for i in range(n - 2, -1, -1):
            if nums[i] <= mx:
                mx = nums[i]
                continue
            k = (nums[i] + mx - 1) // mx # Ceiling division to find number of replacements
            ans += k - 1
            mx = nums[i] // k #Update mx to the largest possible value after replacement
        return ans

Code Implementation (Java)

class Solution {
    public long minimumReplacement(int[] nums) {
        long ans = 0;
        int n = nums.length;
        int mx = nums[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] <= mx) {
                mx = nums[i];
                continue;
            }
            int k = (nums[i] + mx - 1) / mx; // Ceiling division
            ans += k - 1;
            mx = nums[i] / k; //Update mx
        }
        return ans;
    }
}

The implementations in other languages (C++, Go, TypeScript, Rust) follow a very similar structure, adapting the syntax to their respective language features while preserving the core logic of the greedy approach. The key is the right-to-left traversal and the careful calculation of replacements to maintain the maximum possible value at each step.