Watch 10 video solutions for Minimum Replacements to Sort the Array, a hard level problem involving Array, Math, Greedy. This walkthrough by codestorywithMIK has 6,611 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 1051 <= nums[i] <= 109