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 <= 105
1 <= nums[i] <= 109
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:
Complexity | Analysis |
---|---|
Time | O(n) |
Space | O(1) |
Top comments (0)