Non-decreasing Array

Medium
480.

Non-decreasing Array

Non-decreasing Array is a medium coding problem on arrays and greedy, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var checkPossibility = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Count the positions where nums[i-1] > nums[i]. Two or more of them is an immediate false.

  2. Hint 2

    One violation is not automatically fixable — [3,4,2,3] has exactly one and still fails.

  3. 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

  1. Walk i from 1, looking for nums[i-1] > nums[i].
  2. On the second such descent, return false.
  3. On the first: if i < 2 or nums[i-2] <= nums[i], lower nums[i-1] to nums[i] — the cheaper repair, since it keeps the tail small.
  4. Otherwise nums[i-2] > nums[i], so lowering nums[i-1] would break the earlier pair; raise nums[i] to nums[i-1] instead.
  5. Return true if 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 lowering nums[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 True

Java

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