Minimum Operations to Make Array Non Decreasing
Asked at Amazon
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | MEDIUM | View all Amazon questions → |
How to Think About It
Brute force: for each element, replace it with any valid value and recurse — exponential.
Greedy insight: when nums[i] < nums[i-1], you must fix one of them.
Always fix the right element: set nums[i] to nums[i-1] to avoid breaking the previous fix.
Track the previous value and count how many times the current value is strictly less.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 opsFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.