Minimum Replacements to Sort the Array - Video Solutions

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.