Solution: Minimum Replacements to Sort the Array

Statement

You are given a 0-indexed integer array nums. You are allowed to perform the following operation any number of times:

• Select any element in the array and replace it with two positive integers whose sum is equal to the selected element.

For example, if the array is nums = [5, 6, 7], you can choose the element 6 and replace it with 2 and 4, resulting in a new array [5, 2, 4, 7].

Your goal is to make the array sorted in non-decreasing order using the minimum number of operations.

Return the minimum number of operations required to achieve this.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $1 \leq$ nums[i] $\leq 10^5$

Solution

To transform an unsorted array into a non-decreasing sequence using the fewest replacement operations, we must understand how to handle adjacent pairs that violate the sorted order. Specifically, whenever we encounter a pair where nums[i] > nums[i + 1], we must decide which element to modify. The key observation is that we should always break down the larger number (nums[i]) rather than the smaller one (nums[i + 1]). Modifying the smaller value doesn’t help achieve a sorted order and only increases the total number of operations.

Once we’ve determined that we should break down nums[i] when nums[i] > nums[i + 1], the next important design decision is traversal order. To avoid disrupting previously processed elements, we must traverse the array from right to left.

Here’s why:

• By processing elements in reverse order, we ensure that the suffix (i.e., the right-hand part of the array) always remains sorted.

• When we replace nums[i] with smaller values, the resulting elements will be less than or equal to nums[i], and ideally less than or equal to nums[i + 1].

• If we process the array from left to right and replace a larger element with smaller elements, it may disturb the sorted order of the elements already processed on the left, resulting in the need for additional operations to restore the correct order.

With the traversal order established, the next objective is to minimize the number of operations. During the reverse traversal, whenever we encounter an element nums[i] such that nums[i] > nums[i + 1], we need to decide how to split nums[i] into smaller values to maintain a non-increasing sequence.

Possible strategies:

• Splitting into many 1s ensures correctness, but is highly inefficient due to the large number of operations required.

• One approach is to break nums[i] based on the value of nums[i + 1], making the remainder of nums[i] divided by nums[i + 1] the new nums[i]. However, this can sometimes produce a very small value for nums[i]. For instance, splitting 7 results in [1, 3, 3], which forces all earlier elements to be reduced to 1s.

A better approach:

We can refine the above division method to minimize the creation of very small values:

• If nums[i] is divisible by nums[i + 1], split it evenly into elements of size nums[i + 1].

• If not, split nums[i] into k = nums[i] / nums[i + 1] + 1 parts. The goal is to make the smallest part as large as possible, ideally around nums[i] / k, to preserve flexibility for future splits.

  • For example, if nums[i] = 7 and nums[i + 1] = 3, splitting it into [2, 2, 3] (instead of [1, 3, 3]) results in a higher minimum value (2 instead of 1), which is preferable for minimizing future replacements.

We don’t replace nums[i] with all of its parts because the problem only allows in-place replacements, not expanding the array. So, we keep just the maximum part and replace nums[i] with it. This preserves the sorted order while using the fewest changes. Since we split the number into k parts but apply only one, the number of operations is k - 1.

We considered two separate cases for calculating the number of elements to split nums[i] into. However, both cases can be unified with a single formula: k = (nums[i] + nums[i + 1] - 1) / nums[i + 1]. This expression effectively performs a ceiling division, ensuring we always compute the correct number of parts, whether or not nums[i] is divisible by nums[i + 1].

The steps of the algorithm are as follows:

1. Initialize a variable operations to zero to count the total number of operations performed.

2. Traverse the array from right to left, starting from the second last element down to the first element:

   1. For each element nums[i], compare it with the next element nums[i + 1]:

      1. If nums[i] is less than or equal to nums[i + 1], no operation is needed.

      2. Otherwise, proceed to split nums[i]:

         1. Calculate the minimum number of parts to split nums[i] into so that each part is less than or equal to nums[i + 1]. This is done using the formula: parts = (nums[i] + nums[i + 1] - 1) / nums[i + 1]

         2. Increment the operation count by parts - 1, since splitting into parts pieces requires parts - 1 replacement operations.

         3. Update nums[i] to the maximum possible value of the split parts by integer division: nums[i] = nums[i] / parts.

3. Return the total count of operations performed.

Let’s look at the following illustration to get a better understanding of the solution: