DAY 88 - 2366. Minimum Replacements to Sort the Array

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

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⁵
1 <= nums[i] <= 10⁹

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:

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: