2366. Minimum Replacements to Sort the Array LeetCode Solution
In this guide, you will get 2366. Minimum Replacements to Sort the Array LeetCode Solution with the best time and space complexity. The solution to Minimum Replacements to Sort the Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
2366. Minimum Replacements to Sort the Array LeetCode Solution in C++
class Solution {
public:
long long minimumReplacement(vector<int>& nums) {
long ans = 0;
int mx = nums.back();
for (int i = nums.size() - 2; i >= 0; --i) {
const int ops = (nums[i] - 1) / mx;
ans += ops;
mx = nums[i] / (ops + 1);
}
return ans;
}
}; /* code provided by PROGIEZ */
2366. Minimum Replacements to Sort the Array LeetCode Solution in Java
class Solution {
public long minimumReplacement(int[] nums) {
long ans = 0;
int mx = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; --i) {
final int ops = (nums[i] - 1) / mx;
ans += ops;
mx = nums[i] / (ops + 1);
}
return ans;
}
} // code provided by PROGIEZ
2366. Minimum Replacements to Sort the Array LeetCode Solution in Python
class Solution:
def minimumReplacement(self, nums: list[int]) -> int:
ans = 0
mx = nums[-1]
for i in range(len(nums) - 2, -1, -1):
ops = (nums[i] - 1) // mx
ans += ops
mx = nums[i] // (ops + 1)
return ans # code by PROGIEZ
