Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2450. Minimum Replacements to Sort the Array

My accepted Python solution to LeetCode problem 2450, Minimum Replacements to Sort the Array, running in 29ms.

  • Difficulty: Hard
  • Python
  • Runtime 29ms
  • Memory 31.1MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 29ms, memory 31.1MB, accepted 2026-01-02.

python
class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        n = len(nums)
        operations = 0
        prev = nums[-1]  # Start from the end
        
        for i in range(n - 2, -1, -1):
            if nums[i] > prev:
                # Need to split nums[i] into parts all <= prev
                parts = (nums[i] + prev - 1) // prev  # Ceiling division
                operations += parts - 1
                prev = nums[i] // parts  # Smallest part becomes the new limit
            else:
                prev = nums[i]
        
        return operations

Source