Non-decreasing Array — Solution in Python, Java & C++
Non-decreasing Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Non-decreasing Array is a medium coding problem on arrays and greedy, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array nums, return true if it can be made non-decreasing by modifying at most one element.
An array is non-decreasing if nums[i] <= nums[i + 1] holds for every i.
Example 1
Input: nums = [4,2,3]
Output: true
Explanation: Change the 4 to a 1 (or to 2) and the array becomes non-decreasing.
Example 2
Input: nums = [4,2,1]
Output: false
Explanation: Two separate violations — one change cannot fix both.
Example 3
Input: nums = [3,4,2,3]
Output: false
Constraints
1 <= nums.length <= 100000-100000 <= nums[i] <= 100000
Hints for Non-decreasing Array
Hint 1
Count the positions where
nums[i-1] > nums[i]. Two or more of them is an immediatefalse.Hint 2
One violation is not automatically fixable —
[3,4,2,3]has exactly one and still fails.Hint 3
At a violation you must decide which of the two elements to change. Look one step further back:
nums[i-2]decides it.
How to solve Non-decreasing Array
Scan for descents. At most one may occur, and when it does you must repair it in the way that leaves the array most repairable — which depends on the element two positions back.
Approach
- Walk
ifrom1, looking fornums[i-1] > nums[i]. - On the second such descent, return
false. - On the first: if
i < 2ornums[i-2] <= nums[i], lowernums[i-1]tonums[i]— the cheaper repair, since it keeps the tail small. - Otherwise
nums[i-2] > nums[i], so loweringnums[i-1]would break the earlier pair; raisenums[i]tonums[i-1]instead. - Return
trueif the scan finishes.
Why it works
Lowering the left element is always at least as good as raising the right one — it never makes a later comparison harder. It is only unavailable when it would create a new descent with nums[i-2], and in that case raising nums[i] is the sole remaining option.
Complexity
- Time —
O(n) - Space —
O(1) if you modify in place, O(n) on a copy
Pitfalls
- Counting descents alone is not enough:
[3,4,2,3]has one descent and is still impossible. - Always raising
nums[i]fails on[4,2,3]; always loweringnums[i-1]fails on[3,4,2,3]. - The array must actually be mutated as you go — otherwise later comparisons use stale values.
Reference solution
Python
from typing import List
def checkPossibility(nums: List[int]) -> bool:
a = list(nums)
bad = 0
for i in range(1, len(a)):
if a[i - 1] > a[i]:
bad += 1
if bad > 1:
return False
if i < 2 or a[i - 2] <= a[i]:
a[i - 1] = a[i]
else:
a[i] = a[i - 1]
return TrueJava
public static boolean checkPossibility(int[] nums) {
int[] a = nums.clone();
int bad = 0;
for (int i = 1; i < a.length; i++) {
if (a[i - 1] > a[i]) {
bad++;
if (bad > 1) return false;
if (i < 2 || a[i - 2] <= a[i]) a[i - 1] = a[i];
else a[i] = a[i - 1];
}
}
return true;
}C++
bool checkPossibility(vector<int>& nums) {
vector<int> a = nums;
int bad = 0;
for (int i = 1; i < (int) a.size(); i++) {
if (a[i - 1] > a[i]) {
bad++;
if (bad > 1) return false;
if (i < 2 || a[i - 2] <= a[i]) a[i - 1] = a[i];
else a[i] = a[i - 1];
}
}
return true;
}JavaScript
var checkPossibility = function(nums) {
const a = nums.slice();
let bad = 0;
for (let i = 1; i < a.length; i++) {
if (a[i - 1] > a[i]) {
bad++;
if (bad > 1) return false;
if (i < 2 || a[i - 2] <= a[i]) a[i - 1] = a[i];
else a[i] = a[i - 1];
}
}
return true;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms