DAY 88 - 2366. Minimum Replacements to Sort the Array
Tags: leetcode, beginners, algorithms, tutorial
Published: 2023-08-30 18:50:05

Hey Guys! Nayan here and we are going to solve another daily leetcode question. I will be taking you guys from intuition to algorithm so stick with me. Incase you don't understand some parts, please feel free to ask in the comments.

## Question: [Minimum Replacements to Sort the Array](https://leetcode.com/problems/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 <= 10<sup>5</sup>
> 1 <= nums[i] <= 10<sup>9</sup>

## Intuition:
**Let's start with the question observations first:**

- Our final array needs to be sorted in a nondecreasing order.
- We don't need to necessarily return the output array but the minimum operations we need to do it. We can't change the order of current elements unless we replace them.

> **Key Observation:** Our last element can only get smaller if we further break it down so we shall fix our last element.

- Further now that we have fixed our last element, we want to make all elements on the left of it to equal or less than to it.
- We should also update our last element to the smallest value after fixing positions while traversing.
- Keeping this intuition in mind, let's try to derive a solution.

---

## Approach:

- **Initialization:** I initialize a variable ans to keep track of the number of replacements needed and get the total number of elements in the array nums using n.
- **Starting from the End:** I start iterating through the array in reverse order, beginning from the second-to-last element (index n-2). I do this because I need to consider each element in relation to its next element.
- **Comparison with Next Element:** For each element at index i, I check if it is greater than the last element I encountered, which I track using the variable lastElement. If it is indeed greater, it implies that I need to reduce this element to ensure it's less than or equal to the next element.
- **Optimal Replacement Count:** To minimize the number of replacements, I calculate the number of operations needed to reduce the current element to less than or equal to the lastElement. I use the integer division of nums[i] by lastElement, and if there's a remainder, I add 1 to account for the additional operation. This count of operations represents the optimal way to reduce the current element.
- **Updating lastElement:** I update lastElement with the result of nums[i] divided by the calculated operations count. This ensures that after applying these operations, the current element becomes less than or equal to the next element.
- **Counting Replacements:** I increment the ans by the operations count minus 1. The minus 1 is because the first operation doesn't count as a replacement since it's just bringing the element down to the next element's level.
- **Continuing Iteration:** If the current element is not greater than the lastElement, it means I don't need any replacements for this element. I simply update lastElement to the value of the current element.
- **Final Result:** After the iteration completes, the ans variable contains the minimum number of replacements needed to satisfy the conditions.

---

### Code:
```cpp
long long minimumReplacement(vector<int>& nums) {
       long long ans = 0;
       int n = nums.size();
       long long lastElement = nums[n-1];

       for(int i = n-2; i>=0; --i){
           if(nums[i] > lastElement){
               int op = nums[i] /lastElement;
               if(nums[i] % lastElement) op++;
               lastElement = nums[i] / op;
               ans += op -1;
           }
           else{
               lastElement = nums[i];
           }
       }
       return ans;
    }

```

---


### Complexity Analysis:

| Complexity | Analysis |
|------------|----------|
| Time       | O(n)|
| Space      | O(1) |