Non-decreasing Array

Non-decreasing Array

What is this problem about?

The Non-decreasing Array problem asks: given an integer array, can you make it non-decreasing by modifying at most one element? This Non-decreasing Array coding problem requires careful case analysis — when you find a violation (where arr[i] > arr[i+1]), you must decide whether to decrease arr[i] or increase arr[i+1] to fix it without creating new violations.

Why is this asked in interviews?

Cashfree, Meta, Walmart Labs, and Google ask this to test linear scan with careful case analysis. The naive approach — try all single-element changes — is O(n²). The O(n) solution requires reasoning about which element to modify when a violation is found. The array interview pattern is demonstrated here with precision.

Algorithmic pattern used

Greedy single-pass with violation tracking. Traverse the array. On finding arr[i] > arr[i+1]: increment a modification counter. Then decide: if i > 0 and arr[i-1] > arr[i+1], we must increase arr[i+1] to arr[i] (can't decrease arr[i] below arr[i-1]). Otherwise, decrease arr[i] to arr[i+1]. If modifications > 1, return false. After the loop, return true.

Example explanation

Array: [4, 2, 3]. Violation at i=0 (4>2).

• i-1 doesn't exist, so decrease arr[0] to 2 → [2,2,3]. 1 modification.
• Continue: no more violations. Return true.

Array: [3, 4, 2, 3]. Violation at i=1 (4>2).

• arr[i-1]=3 > arr[i+1]=2: can't decrease 4 below 3 or increase 2... must increase arr[2] to 4 → [3,4,4,3].
• Continue: violation at i=2 (4>3). 2 modifications → return false.

Common mistakes candidates make

• Performing the actual array modification and continuing the scan (must update the virtual value correctly).
• Not checking arr[i-1] > arr[i+1] when deciding which element to modify.
• Using O(n²) brute force: try all single deletions/modifications.
• Counting violations instead of modifications (one violation may require a specific fix that creates another).

Interview preparation tip

The key insight for this problem is the greedy choice when a violation is found: prefer decreasing arr[i] (preserve the smaller arr[i+1]) unless the previous element forces you to increase arr[i+1]. Always update the effective value of the modified element so subsequent comparisons are correct. Practice this problem with multiple violation types to build confidence in the case analysis. It's a good O(n) greedy warm-up before harder interval problems.