← Back to Index

📚 Minimum Replacements to Sort the Array – Java Cheat Sheet

📌 What Is It?

The Minimum Replacements to Sort the Array problem involves modifying an array such that it becomes non-decreasing. You can replace any element with two or more integers that sum up to the original element. The goal is to minimize the number of replacements required.

🧱 Pattern Template

Greedy Algorithm (Reverse Traversal)

class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        long replacements = 0;
        int prev = nums[n - 1]; // Start with the last element

        // Traverse the array from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] > prev) {
                // Calculate the number of parts needed
                int parts = (nums[i] + prev - 1) / prev;
                replacements += parts - 1;
                prev = nums[i] / parts; // Update prev to the largest valid part
            } else {
                prev = nums[i]; // No replacement needed
            }
        }

        return replacements;
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(N), where N is the length of the array.
• Space Complexity: O(1), as no additional space is used.

✅ Use Cases

• Optimizing operations to make an array non-decreasing.
• Solving problems involving array manipulation and constraints.

📘 Common LeetCode Problems

• 2366. Minimum Replacements to Sort the Array [Hard] Greedy

🧪 Example

Input: nums = [5, 4, 3, 2, 1]
Output: 10

Explanation:
- Replace 5 with [2, 3].
- Replace 4 with [2, 2].
- Replace 3 with [2, 1].
- Replace 2 with [1, 1].
- Total replacements = 10.

💡 Pro Tips

• Traverse the array from right to left to ensure the array remains non-decreasing.
• Use integer division to calculate the number of parts needed for each replacement.
• Update the `prev` variable to the largest valid part after each replacement.