# Minimum Replacements to Sort the Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-replacements-to-sort-the-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-replacements-to-sort-the-array
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [PayPal](https://scaleengineer.com/companies/paypal)
---
## 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 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`

# Approaches
## Naive Greedy Approach (Right-to-Left)
A less optimal greedy approach is to iterate through the array from right to left. When an element `nums[i]` is found to be greater than the element to its right (`next_val`), we must split `nums[i]`. A simple, but naive, way to split `nums[i]` is to break it down into pieces that are mostly of size `next_val`. This strategy, while seemingly logical, makes a poor choice for the new constraint on the next element, leading to a suboptimal total number of operations.
**Time:** O(N), where N is the number of elements in the array. We perform a single pass through the array. · **Space:** O(1), as we only use a few variables to store the running count of operations and the next value constraint.
**Pros:** The approach is simple to understand.; It correctly identifies the necessary condition for splitting.; It has an efficient time and space complexity.
**Cons:** This greedy strategy is not optimal. It does not guarantee the minimum number of replacements because its choice of the next constraint (`next_val`) is too strict, potentially increasing future operations.
### Explanation
This approach processes the array from right to left, ensuring that each element is less than or equal to the element that follows it. When `nums[i] > next_val`, where `next_val` is the value of the subsequent element (or the first part of it if it was split), `nums[i]` must be broken down.

The naive splitting strategy is as follows: break `nums[i]` into `q = floor(nums[i] / next_val)` pieces of size `next_val`, and one remainder piece `r = nums[i] % next_val`. For example, if `nums[i] = 19` and `next_val = 8`, we split `19` into `3, 8, 8`. This requires `q=2` operations. The new constraint for `nums[i-1]` becomes the smallest piece of this split, which is `r=3` (or `next_val` if `r=0`).

This choice is suboptimal because making the new constraint (`next_val`) as small as `nums[i] % next_val` can cause a cascade of additional, unnecessary splits for elements to the left.

```java
class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        long operations = 0;
        long next_val = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= next_val) {
                next_val = nums[i];
                continue;
            }

            long current_val = nums[i];
            // This calculation finds the number of operations based on this naive split.
            // It's equivalent to floor(current_val / next_val) if there's a remainder,
            // and floor(current_val / next_val) - 1 if there's no remainder.
            long num_ops = (current_val - 1) / next_val;
            operations += num_ops;
            
            // The new constraint for the left element is the remainder of the division.
            long remainder = current_val % next_val;
            next_val = (remainder == 0) ? next_val : remainder;
        }

        return operations;
    }
}
```
### Algorithm
1. Initialize `operations = 0` and `next_val = nums[n-1]`.
2. Iterate from `i = n-2` down to `0`.
3. If `nums[i] <= next_val`, the array is locally sorted. Update `next_val = nums[i]` and continue.
4. If `nums[i] > next_val`, a split is necessary.
5. Calculate operations needed for a naive split: `ops_needed = (nums[i] - 1) / next_val`. Add this to `operations`.
6. Update `next_val` for the next iteration. The new `next_val` is `nums[i] % next_val`. If the remainder is 0, it's `next_val` itself.
7. Return total `operations`.

## Optimal Greedy Approach (Right-to-Left)
The most efficient and correct approach is a greedy algorithm that processes the array from right to left. By doing so, any decision to split an element `nums[i]` only depends on the element to its right, `nums[i+1]` (or its resulting pieces), and does not affect the already processed suffix of the array. The key is to make a locally optimal choice that is also globally optimal. This involves minimizing the number of splits for the current element while maximizing the value of the first resulting piece to relax the constraint for the next element.
**Time:** O(N), where N is the number of elements in `nums`. The algorithm involves a single pass over the array from right to left. · **Space:** O(1). The algorithm uses only a few variables to keep track of the state (`operations`, `next_val`), regardless of the input size.
**Pros:** This approach is guaranteed to find the minimum number of replacements.; It is highly efficient, with linear time complexity and constant space complexity.
**Cons:** The logic for calculating the number of pieces and the next constraint is slightly more involved than a naive approach, but it's essential for correctness.
### Explanation
We traverse the array from the second-to-last element to the first. We maintain a variable, `next_val`, which holds the value that the current element `nums[i]` must be less than or equal to. Initially, `next_val` is `nums[n-1]`.

For each element `nums[i]`, we check if `nums[i] <= next_val`. 
- If it is, no operation is needed for this element. We update `next_val` to `nums[i]` because the element to the left, `nums[i-1]`, must now be less than or equal to the new, smaller value `nums[i]`.
- If `nums[i] > next_val`, we must split `nums[i]` into smaller pieces. To minimize operations, we must split it into the minimum number of pieces, `k`. Each piece must be at most `next_val`. The minimum `k` is `ceil(nums[i] / next_val)`. This split requires `k-1` operations.

After splitting `nums[i]` into `k` pieces, the new constraint for `nums[i-1]` is the value of the first (and smallest) piece of the split. To give `nums[i-1]` the most 'room' and potentially avoid splitting it, we want this first piece to be as large as possible. This is achieved by making the `k` pieces as equal as possible. The smallest piece in such a distribution is `floor(nums[i] / k)`. This becomes our new `next_val`.

This greedy choice is optimal because at each step we (1) perform the minimum operations required for the current element and (2) create the least restrictive condition for the subsequent elements.

```java
class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        long operations = 0;
        // The value that the current element must be less than or equal to.
        long next_val = nums[n - 1];

        // We iterate from right to left.
        for (int i = n - 2; i >= 0; i--) {
            // If the current element is already in order, no operations needed.
            // Update next_val for the element to the left.
            if (nums[i] <= next_val) {
                next_val = nums[i];
                continue;
            }

            // If the current element is larger, we must split it.
            long current_val = nums[i];

            // Calculate how many pieces we need to split current_val into.
            // Each piece must be <= next_val.
            // k = ceil(current_val / next_val)
            long k = (current_val + next_val - 1) / next_val;

            // Splitting into k pieces requires k-1 operations.
            operations += k - 1;

            // The new constraint for the element to the left is the smallest possible
            // first piece, which we maximize by distributing current_val as evenly as possible.
            // new_next_val = floor(current_val / k)
            next_val = current_val / k;
        }

        return operations;
    }
}
```
### Algorithm
1. Initialize `operations = 0` and `next_val = nums[n-1]`.
2. Iterate from `i = n-2` down to `0`.
3. If `nums[i] <= next_val`, update `next_val = nums[i]` and proceed to the next element.
4. If `nums[i] > next_val`, we must perform replacements:
  a. Calculate the minimum number of pieces `k` to split `nums[i]` into, such that each piece is `<= next_val`. This is `k = ceil(nums[i] / next_val)`, which can be calculated using integer arithmetic as `(nums[i] + next_val - 1) / next_val`.
  b. Add `k - 1` to `operations`, as splitting into `k` pieces takes `k - 1` operations.
  c. Update `next_val` for the next element on the left. To be least restrictive, we want the first piece of the split to be as large as possible. This is achieved by making the pieces as equal as possible. The new `next_val` will be `floor(nums[i] / k)`.
5. After the loop, return the total `operations`.

# Solutions
### Java

```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;
      ans += k - 1;
      mx = nums[i] / k;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long minimumReplacement(vector<int> &nums) {
    long long ans = 0;
    int n = nums.size();
    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;
      ans += k - 1;
      mx = nums[i] / k;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumReplacement(self, nums: List[int]) -> int: ans = 0 n = len(nums) mx = nums[- 1] for i in range(n - 2, - 1, - 1): if nums[i] <= mx: mx = nums[i] continue k = (nums[i] + mx - 1) // mx ans += k - 1 mx = nums[i] // k return ans

```