Minimum Replacements to Sort the Array solution and explanation
Google
9 more videos on this problem
Minimum Replacements to Sort the Array | Cleanest Code | Full Dry Run | GOOGLE | Leetcode - 2366codestorywithMIK · 30:57 · 11K views
2366. Minimum Replacements to Sort the Array II Greedy II Leetcode 2366Aryan Mittal · 17:57 · 5K views
Biweekly Contest 84 | 6144. Minimum Replacements to Sort the ArraycodingMohan · 14:44 · 3K views
2366. Minimum Replacements to Sort the Array (Leetcode Hard)Programming Live with Larry · 18:32 · 1K views
Minimum Replacements to Sort the Array - Greedy - PythonCheatCode Ninja · 9:14 · 1K views
Leetcode 2366: Minimum Replacements to Sort the ArrayAlgorithms Casts · 20:20 · 1K views
Minimum Replacements to Sort the Array| Google |Daily Leetcode Challenge | Leetcode 2366 | HardLet's Code Together · 10:08 · 574 views
Crack LeetCode 2366. Minimum Replacements to Sort the Array - Greedy with Dynamic Upper BoundvanAmsen · 9:14 · 523 views
Daily Leetcode #1247: Aug 30, 2023 - 2366. Minimum Replacements to Sort the ArrayProgramming Live with Larry · 38:48 · 387 views
Minimum Replacements to Sort the Array | LEETCODE | DSA | ARRAY | ADHOCtechymon · 10:19 · 203 views
The problem
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 replacenums[1]with2and4and convertnumsto[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
Approach overview
Problem Overview: You are given an integer array and may replace any element with two or more positive integers that sum to it. The goal is to perform the minimum number of replacements so the final array becomes non‑decreasing. Each replacement increases the array length, so the challenge is choosing how many parts each element should be split into while keeping the order valid.
Approach 1: Reverse Approach with Priority Queue (O(n log n) time, O(n) space)
This method processes the array from right to left while maintaining the current allowed maximum value using a priority queue. If the current element is larger than the next allowed value, it must be split into smaller parts. The idea is to repeatedly divide the number so that every generated piece is less than or equal to the next value in the sorted order. Each split contributes to the replacement count, and the resulting pieces are pushed into the heap to maintain ordering. The heap ensures the smallest valid constraint propagates backward while iterating. This approach is conceptually straightforward but introduces O(log n) heap operations for each adjustment.
Approach 2: Greedy Strategy with Two-Pointer Technique (O(n) time, O(1) space)
The optimal strategy scans the array from right to left and keeps track of the maximum allowed value for the current position. Start with the last element as the limit. For each previous element nums[i], check if it already satisfies nums[i] ≤ limit. If it does, simply update the limit to nums[i]. Otherwise, split the value into the minimum number of parts so each part is ≤ limit. The number of required pieces is k = ceil(nums[i] / limit). That means k - 1 replacements are needed. After splitting, the new limit becomes floor(nums[i] / k), which is the largest value each piece can take while keeping the array non‑decreasing.
This greedy insight works because the right side of the array is already fixed. You only need to ensure each element on the left does not violate the current bound. By minimizing the number of pieces at every step, you guarantee the global minimum number of operations. The algorithm uses simple arithmetic and a single backward pass, making it extremely efficient.
Recommended for interviews: Interviewers expect the greedy reverse traversal. It demonstrates strong reasoning about constraints and optimal partitioning. A heap‑based approach shows the intuition behind maintaining order, but the O(n) greedy solution with arithmetic splitting is the cleanest and most efficient. Understanding how the bound propagates backward is key when working with greedy strategies on array problems that involve value partitioning and math reasoning.
Approach 1: Reverse Approach with Priority Queue
This approach works by iterating from the end of the array to the beginning. The idea is to ensure each element is not bigger than the rest of the previously sorted part of the array. This can be optimized using a priority queue to store the required values efficiently, making it easier to decide where to split large numbers.
Whenever we find a number that is greater than the required maximum, we split it and keep track of splits using the priority queue (min-heap in this case).
import heapq
def min_replacements(nums):
pq = []
operations = 0
for num in reversed(nums):
if pq and num > pq[0]:
operations += 1
half = num // 2
heapq.heappush(pq, half)
heapq.heappush(pq, half + num % 2)
else:
heapq.heappush(pq, num)
return operations
# Example usage
print(min_replacements([3, 9, 3])) # Output: 2
print(min_replacements([1, 2, 3, 4, 5])) # Output: 0function minReplacements(nums) {
let pq = [];
let operations = 0;
for (let i = nums.length - 1; i >= 0; i--) {
if (pq.length && nums[i] > pq[0]) {
operations++;
let half = Math.floor(nums[i] / 2);
pq.push(half);
pq.push(half + nums[i] % 2);
pq.sort((a, b) => a - b);
} else {
pq.push(nums[i]);
}
}
return operations;
}
// Example usage
console.log(minReplacements([3, 9, 3])); // Output: 2
console.log(minReplacements([1, 2, 3, 4, 5])); // Output: 0The solution uses a priority queue to manage elements efficiently. By iterating the array from end to start, we can ensure that each number is processed in a priority-wise manner, allowing us to minimize operations by only splitting when necessary.
Time Complexity: O(N log N), primarily due to the heap operations.
Space Complexity: O(N) due to the additional space used by the priority queue.
Approach 2: Greedy Strategy with Two-Pointer Technique
This approach relies on a greedy approach combined with a two-pointer technique. The algorithm will scan the array while managing smaller replacements for larger numbers. The idea is to minimize the change needed by checking previous and current indices simultaneously to determine necessary operations.
#include <vector>
#include <algorithm>
int minReplacements(std::vector<int>& nums) {
int operations = 0;
int n = nums.size();
std::vector<int> small;
for (int i = n - 1; i >= 0; --i) {
if (!small.empty() && nums[i] > small.back()) {
operations++;
int half = nums[i] / 2;
small.push_back(half);
small.push_back(half + nums[i] % 2);
std::sort(small.begin(), small.end());
} else {
small.push_back(nums[i]);
}
}
return operations;
}
// Example usage
#include <iostream>
int main() {
std::vector<int> nums1 = {3, 9, 3};
std::cout << minReplacements(nums1) << std::endl; // Output: 2
std::vector<int> nums2 = {1, 2, 3, 4, 5};
std::cout << minReplacements(nums2) << std::endl; // Output: 0
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int MinReplacements(int[] nums) {
int operations = 0;
List<int> small = new List<int>();
for (int i = nums.Length - 1; i >= 0; i--) {
if (small.Count > 0 && nums[i] > small[0]) {
operations++;
int half = nums[i] / 2;
small.Add(half);
small.Add(half + nums[i] % 2);
small.Sort();
} else {
small.Add(nums[i]);
}
}
return operations;
}
//Example usage
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinReplacements(new int[] { 3, 9, 3 })); // Output: 2
Console.WriteLine(sol.MinReplacements(new int[] { 1, 2, 3, 4, 5 })); // Output: 0
}
}The C++ solution uses a vector to maintain the smaller elements found during the traversal from end to start of the array, making controlled adjustments to ensure non-decreasing order.
We maintain order using sorting and check conditions dynamically while iterating.
Time Complexity: O(N^2) with sorting for maintaining order.
Space Complexity: O(N) due to the auxiliary vector space used.
Approach 3: Greedy Approach
We observe that to make the array nums non-decreasing or monotonically increasing, the elements towards the end of the array should be as large as possible. Therefore, it is unnecessary to replace the last element nums[n-1] of the array nums with multiple smaller numbers.
In other words, we can traverse the array nums from the end to the beginning, maintaining the current maximum value mx, initially mx = nums[n-1].
- If the current element
nums[i] leq mx, there is no need to replacenums[i]. We simply updatemx = nums[i]. - Otherwise, we need to replace
nums[i]with multiple numbers that sum tonums[i]. The maximum of these numbers ismx, and the total number of replacements isk=\left \lceil \frac{nums[i]}{mx} \right \rceil. Therefore, we need to performk-1operations, which are added to the answer. Among theseknumbers, the smallest number is\left \lfloor \frac{nums[i]}{k} \right \rfloor. Therefore, we updatemx = \left \lfloor \frac{nums[i]}{k} \right \rfloor.
After the traversal, we return the total number of operations.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
class Solution {
public long minimumReplacement(int[] nums) {
long ans = 0;
int n = nums.length;
int mx = nums[n - 1];
for (int i = n - 2; i >= 0; --i) {
if (nums[i] <= mx) {
mx = nums[i];
continue;
}
int k = (nums[i] + mx - 1) / mx;
ans += k - 1;
mx = nums[i] / k;
}
return ans;
}
}function minimumReplacement(nums: number[]): number {
const n = nums.length;
let mx = nums[n - 1];
let ans = 0;
for (let i = n - 2; i >= 0; --i) {
if (nums[i] <= mx) {
mx = nums[i];
continue;
}
const k = Math.ceil(nums[i] / mx);
ans += k - 1;
mx = Math.floor(nums[i] / k);
}
return ans;
}func minimumReplacement(nums []int) (ans int64) {
n := len(nums)
mx := nums[n-1]
for i := n - 2; i >= 0; i-- {
if nums[i] <= mx {
mx = nums[i]
continue
}
k := (nums[i] + mx - 1) / mx
ans += int64(k - 1)
mx = nums[i] / k
}
return
}impl Solution {
#[allow(dead_code)]
pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
if nums.len() == 1 {
return 0;
}
let n = nums.len();
let mut max = *nums.last().unwrap();
let mut ret = 0;
for i in (0..=n - 2).rev() {
if nums[i] <= max {
max = nums[i];
continue;
}
// Otherwise make the substitution
let k = (nums[i] + max - 1) / max;
ret += (k - 1) as i64;
// Update the max value, which should be the minimum among the substitution
max = nums[i] / k;
}
ret
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Reverse Approach with Priority Queue | Time Complexity: O(N log N), primarily due to the heap operations. |
| Greedy Strategy with Two-Pointer Technique | Time Complexity: O(N^2) with sorting for maintaining order. |
| Greedy Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse with Priority Queue | O(n log n) | O(n) | When simulating the splitting process explicitly and maintaining ordering via a heap |
| Greedy Reverse Traversal (Two-Pointer Style) | O(n) | O(1) | Optimal interview solution; single backward pass with arithmetic partitioning |
| Naive Simulation | O(n²) | O(n) | Educational baseline to understand why greedy partitioning is necessary |
Frequently asked questions
Is Minimum Replacements to Sort the Array easy or hard?
LeetCode classifies this problem as Hard because the greedy insight is not obvious. Many initial attempts simulate splitting operations or use heaps, which leads to slower solutions. Recognizing that the array should be processed from right to left with a dynamic upper bound unlocks the optimal O(n) approach.
Minimum Replacements to Sort the Array Python/Java solution
Most implementations follow the same greedy idea regardless of language. Python and Java solutions iterate from the end of the array, compute k = ceil(num / limit), add k−1 operations, and update the limit to num // k. The logic translates directly to C++, JavaScript, and C# with identical O(n) complexity.
How to solve Minimum Replacements to Sort the Array in O(n)?
Traverse the array from the end and keep a variable representing the maximum allowed value. If the current element is larger than this bound, compute how many parts it must be split into using ceil(num / limit). Add k−1 to the replacement count and update the limit to floor(num / k). This ensures every generated value keeps the array non-decreasing.
What is the best approach for Minimum Replacements to Sort the Array?
The greedy reverse traversal is the best approach. Iterate from right to left and maintain the maximum allowed value for the current position. If a number exceeds this limit, split it into k parts where k = ceil(num / limit). This produces the minimum number of replacements and runs in O(n) time with O(1) extra space.
Is Minimum Replacements to Sort the Array asked at Google/Amazon/Meta?
Greedy array partitioning problems like this appear in interviews at companies such as Google, Amazon, and Meta. The question tests the ability to derive a mathematical greedy rule and reason about minimizing operations under ordering constraints.
What data structure is used in Minimum Replacements to Sort the Array?
The optimal solution mainly relies on greedy logic and arithmetic rather than complex data structures. Some alternative implementations use a priority queue to manage generated parts while processing elements in reverse order, but this increases complexity to O(n log n).
What is the time complexity of Minimum Replacements to Sort the Array?
The optimal greedy solution runs in O(n) time because the array is scanned once from right to left. Each element requires constant-time arithmetic to determine the number of splits. Space complexity is O(1) since only a few variables are maintained during traversal.