Minimum Replacements to Sort the Array - Practice Coding Problems

Minimum Replacements to Sort the Array - 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 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.

Input & Output

Example 1 — Basic Split Case

$ Input: nums = [3,9,4]

› Output: 2

💡 Note: 9 > 4, so we need to split 9. Optimal split: 9 → 3+3+3 (2 operations). Array becomes [3,3,3,3,4] which is sorted.

Example 2 — Already Sorted

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

› Output: 0

💡 Note: Array is already in non-decreasing order, no operations needed.

Example 3 — Multiple Splits

$ Input: nums = [2,10,20]

› Output: 6

💡 Note: 20→5+5+5+5 (3 ops), then 10→3+3+4 (2 ops), then 2→1+1 (1 op). Total: 6 operations.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Unsorted array [3,9,4] where 9 > 4 violates order

Process

Split 9 into 3 equal parts: 3+3+3 (2 operations)

Output

Sorted array [3,3,3,3,4] with 2 operations

Key Takeaway

🎯 Key Insight: Work backwards and split each violating element into the minimum number of equal parts

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to work backwards from right to left, greedily splitting each element into the minimum number of pieces needed. When we encounter nums[i] > nums[i+1], we split nums[i] into ⌈nums[i]/nums[i+1]⌉ equal parts. Best approach is Greedy. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Recursion	O(2^n)	O(n)	Try all possible ways to split elements and find minimum operations
Greedy (Optimal)	O(n)	O(1)	Work backwards, greedily split elements to minimize total operations

Brute Force with Recursion — Algorithm Steps

Start from left, check if current element ≤ next element
If not, try all ways to split current element into two parts
Recursively solve for each split possibility
Return minimum operations across all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Order

Find first element violating non-decreasing order

Try Splits

Recursively try all ways to split that element

Count Operations

Return minimum operations across all possibilities

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solve(int* arr, int size, int index) {
    if (index >= size - 1) {
        return 0;
    }
    
    if (arr[index] <= arr[index + 1]) {
        return solve(arr, size, index + 1);
    }
    
    int minOps = INT_MAX;
    int current = arr[index];
    
    for (int split1 = 1; split1 < current; split1++) {
        int split2 = current - split1;
        if (split1 <= split2) {
            int* newArr = (int*)malloc((size + 1) * sizeof(int));
            int newSize = size + 1;
            
            for (int i = 0; i < index; i++) {
                newArr[i] = arr[i];
            }
            newArr[index] = split1;
            newArr[index + 1] = split2;
            for (int i = index + 1; i < size; i++) {
                newArr[i + 1] = arr[i];
            }
            
            int ops = 1 + solve(newArr, newSize, index);
            if (ops < minOps) {
                minOps = ops;
            }
            free(newArr);
        }
    }
    
    return minOps == INT_MAX ? 0 : minOps;
}

int solution(int* nums, int size) {
    return solve(nums, size, 0);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each element can be split in multiple ways, leading to exponential branching

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to array length

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler