HardArrayMathGreedyUpdated Sep 2026

2366. Minimum Replacements to Sort the Array

Asked at Salesforce

Difficulty

Hard

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get an integer array nums. In one operation you may pick any element and split it into two positive integers that add up to it. The two new numbers take its place in the array, so the array grows by one element.

Return the minimum number of operations needed so the final array is sorted in non-decreasing order (each element is less than or equal to the one after it).

Splitting an element into k equal-ish parts costs k - 1 operations. The key insight: when you split a value x into k parts, the smallest part you can make is x // k, and you want the parts to be as large as possible while still fitting under the next element.

Splitting an element into parts

nums393012Start: the 9 is bigger than the 3 that follows it, soit must be split.after split33630123Split 9 into 3 + 6. Now 6 is still bigger than thetrailing 3.after split3333301234Split 6 into 3 + 3. The array is now non-decreasing,using 2 operations.
One operation replaces a value with two values that sum to it, and the array gets one element longer.

Constraints

  • ●1 <= nums.length <= 10^5
  • ●1 <= nums[i] <= 10^9

Examples

Example 1
Inputnums = [3,9,3]
Output2
WhyThe 9 must come down to fit before the final 3. Split 9 into 3 and 6 (1 operation), giving [3,3,6,3]. Now 6 is still bigger than the 3 after it, so split 6 into 3 and 3 (1 more operation), giving [3,3,3,3,3]. That is 2 operations total, and the array is sorted.
Example 2
Inputnums = [1,2,3,4,5]
Output0
WhyThe array is already non-decreasing, so no splits are needed.

Asked At

1 companies
CompanyDifficulty
SalesforceHardView all Salesforce questions →

How to Think About It

1

Brute force: try all possible replacements for each element and check if the array becomes sorted — exponential.

2

Think greedily from right to left: the last element should be as small as possible.

3

For each element arr[i], find the smallest value v such that v ≤ arr[i+1] and v divides arr[i].

4

The minimum replacements for arr[i] is ceil(arr[i] / arr[i+1]) - 1, using integer division.

5

Process from right to left, keeping track of the current maximum allowed value for each position.

Optimal Approach

Process the array from right to left. Maintain a variable representing the maximum allowed value for the current position. For each element arr[i], compute how many replacements are needed: the minimum value we can place is arr[i] divided by ceil(arr[i] / arr[i+1]). The number of replacements is ceil(arr[i] / arr[i+1]) - 1. Update the maximum allowed value for the next (leftward) element. Sum all replacements across the array. This greedy approach works because making elements as large as possible at each step minimizes the total replacements.

Greedy from right to left

nums393012iStart at the last element; it never needs to change.nums393012limit = 3For 9 with limit 3: k = ceil(9/3) = 3 parts, cost 3-1= 2, and the new value is 9 // 3 = 3.nums333012limit = 3For 3 with limit 3: 3 <= 3, so no split and cost 0.Total = 2.k = ceil(nums[i] / nums[i+1])cost += k - 1nums[i] = nums[i] // k
Walk backwards, and for each element compute how many equal-ish parts it needs to stay at or below the element to its right.
ComplexityTime O(n)Space O(1)One right-to-left pass, each element handled with a constant number of arithmetic steps.

What Trips People Up in Real Interviews

1

Clarify that you can only replace an element with its divisors (not arbitrary smaller values).

2

Ask whether the array must be strictly increasing or non-decreasing (allows equal elements).

3

Explain the greedy insight: process from right to left to minimize the number of replacements.

4

Handle edge cases: single element arrays, already sorted arrays, and large values.

5

Discuss that the time complexity is O(n log M) where M is the max element value for finding divisors.

Solution Code

O(n) time
import math

def min_replacements(arr):
    n = len(arr)
    replacements = 0
    for i in range(n - 2, -1, -1):
        if arr[i] > arr[i + 1]:
            k = math.ceil(arr[i] / arr[i + 1])
            replacements += k - 1
            arr[i] = arr[i] // k
    return replacements

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Replacements to Sort the Array problem?

Given an array of positive integers, you can replace any element with any of its divisors (smaller values that divide it evenly). Find the minimum number of replacements needed to make the array non-decreasing. The greedy strategy is to process from right to left, replacing each element with the smallest divisor that keeps it ≤ the next element.

How do you solve Minimum Replacements to Sort the Array?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Replacements to Sort the Array?

Minimum Replacements to Sort the Array is asked at Salesforce. It is a hard difficulty problem.

What are common mistakes on Minimum Replacements to Sort the Array?
  • Clarify that you can only replace an element with its divisors (not arbitrary smaller values).
  • Ask whether the array must be strictly increasing or non-decreasing (allows equal elements).
  • Explain the greedy insight: process from right to left to minimize the number of replacements.
  • Handle edge cases: single element arrays, already sorted arrays, and large values.
  • Discuss that the time complexity is O(n log M) where M is the max element value for finding divisors.