MediumArrayGreedyUpdated Sep 2026

3914. Minimum Operations to Make Array Non Decreasing

Asked at Amazon

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You are given an integer array nums. In one operation you pick any subarray nums[l..r] and add the same positive integer x to every element inside it. You may pick x freely for each operation.

Your goal is to make the whole array non-decreasing, meaning nums[i] <= nums[i+1] for every neighbouring pair. Among all ways to reach that goal, return the smallest possible total of all the x values you used. The number of operations is not limited — only the sum of the x values matters.

A useful way to think about it: raising a subarray is like lifting a block of elements together. To fix a drop, you must lift the part that comes after it.

Lift blocks to remove drops

nums33210123Indices 2 and 3 are below their left neighbour, so thearray is not non-decreasingafter33330123Adding 1 to [2..3] and then 1 to [3..3] costs 2 intotal and makes every step flat
In [3,3,2,1] the values fall twice, and each fall must be lifted by adding to a subarray.

Constraints

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

Examples

Example 1
Inputnums = [3,3,2,1]
Output2
WhyAdd 1 to the subarray [2..3], giving [3,3,3,2]. Then add 1 to the single element at index 3, giving [3,3,3,3]. The total of x is 1 + 1 = 2, and no cheaper plan exists.
Example 2
Inputnums = [5,1,2,3]
Output4
WhyAdd 4 to the subarray [1..3], giving [5,5,6,7]. The total of x is 4. You cannot use less, because the first element 5 forces everything after it up by at least 4.

Asked At

1 companies
CompanyDifficulty
AmazonMediumView all Amazon questions →

How to Think About It

1

Brute force: for each element, replace it with any valid value and recurse — exponential.

2

Greedy insight: when nums[i] < nums[i-1], you must fix one of them.

3

Always fix the right element: set nums[i] to nums[i-1] to avoid breaking the previous fix.

4

Track the previous value and count how many times the current value is strictly less.

5

Keep a running "previous" and increment operations when nums[i] is less than the previous value.

Optimal Approach

Iterate through the array. Maintain the previous element. Whenever the current element is strictly less than the previous, increment the operation count and do not advance the previous value (effectively setting the current element to the previous value). This greedy approach ensures each fix is locally optimal and yields the minimum total operations in O(n) time.

Greedy pass with a running ceiling

nums33210123prevStart with prev = 3, total = 0nums33210123prev3 >= 3, so prev stays 3; then 2 < 3, so add 1 to thetotal and keep prev = 3nums33210123prev1 < 3 again, so add 1 more; total is now 2if nums[i] < prev: total += 1else: prev = nums[i]
Keep the last value that is already valid; every smaller value costs the gap and does not raise the ceiling.
ComplexityTime O(n)Space O(1)One left-to-right pass with a single running value; the cost comes from visiting each element once.

What Trips People Up in Real Interviews

1

Clarify that you can replace with any positive integer, not just a specific value.

2

The optimal fix when nums[i] < nums[i-1] is to set nums[i] = nums[i-1] to minimize downstream issues.

3

Walking through [5, 3, 4, 2, 1] step by step helps the interviewer follow your logic.

4

Edge case: already non-decreasing array requires zero operations.

5

Mention that a single pass O(n) solution exists with greedy reasoning.

Solution Code

O(n) time
def minOperations(nums: list[int]) -> int:
    ops = 0
    prev = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < prev:
            ops += 1
        else:
            prev = nums[i]
    return ops

Pro at DSA?

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

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Operations to Make Array Non Decreasing problem?

Given an integer array, in one operation you can choose an index and replace the value with any positive integer. Return the minimum number of operations to make the array non-decreasing.

How do you solve Minimum Operations to Make Array Non Decreasing?

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 Operations to Make Array Non Decreasing?

Minimum Operations to Make Array Non Decreasing is asked at Amazon. It is a medium difficulty problem.

What are common mistakes on Minimum Operations to Make Array Non Decreasing?
  • Clarify that you can replace with any positive integer, not just a specific value.
  • The optimal fix when nums[i] < nums[i-1] is to set nums[i] = nums[i-1] to minimize downstream issues.
  • Walking through [5, 3, 4, 2, 1] step by step helps the interviewer follow your logic.
  • Edge case: already non-decreasing array requires zero operations.
  • Mention that a single pass O(n) solution exists with greedy reasoning.