Non-decreasing Array solution and explanation
Google
9 more videos on this problem
Non-Decreasing Array - Leetcode 665 - PythonNeetCode · 10:59 · 68K views
Non-decreasing Array | Live Coding with Explanation | Leetcode - 665Algorithms Made Easy · 7:43 · 15K views
(Remade) Non-Decreasing Array | Leetcode 665Nideesh Terapalli · 4:58 · 7K views
Non-decreasing Array | LeetCode 665 | C++, Java, PythonKnowledge Center · 27:45 · 4K views
Non-decreasing Array | LeetCode 665 | Coders CampCoders Camp · 6:20 · 2K views
Non-decreasing Array | Leetcode 665 | Live coding session | LC 665Coding Decoded · 8:03 · 1K views
Leetcode - Non-decreasing Array (Python)Timothy H Chang · 6:01 · 1K views
Leetcode 665 Non-decreasing Array | | Checkout Coding Decoded SDE SheetCoding Decoded · 2:16 · 1K views
Leetcode 665. Non-decreasing Array (Solution+Explanation)ultcode · 7:56 · 690 views
665. Non-decreasing Array (Leetcode Easy)Programming Live with Larry · 19:00 · 593 views
The problem
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).
Example 1:
Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: nums = [4,2,1] Output: false Explanation: You cannot get a non-decreasing array by modifying at most one element.
Constraints:
n == nums.length1 <= n <= 104-105 <= nums[i] <= 105
Approach overview
Problem Overview: You are given an integer array and allowed to modify at most one element. The goal is to determine whether the array can become non-decreasing (each element ≤ next element) after at most one modification.
Approach 1: Single Pass Greedy (O(n) time, O(1) space)
Scan the array once and track how many times the non-decreasing property is violated. A violation occurs when nums[i] < nums[i-1]. You can fix at most one such violation by modifying either nums[i-1] or nums[i]. The key insight is choosing the safer modification: if nums[i] >= nums[i-2], adjust the previous value; otherwise adjust the current one. This greedy decision ensures earlier ordering remains valid while keeping future comparisons safe. The algorithm performs a single linear pass over the array and stores only a counter, resulting in O(n) time and O(1) extra space.
Approach 2: Two-Pointer Strategy (O(n) time, O(1) space)
Use two indices while scanning the array to detect the first position where the order breaks. Once a violation is found, examine surrounding values to decide whether adjusting the left element or the right element would restore the non-decreasing condition. This approach still iterates through the array once but explicitly reasons about neighboring elements using pointer comparisons. The logic resembles patterns used in two pointers problems where local structure determines the correction. Because only constant variables are used and each element is processed once, the complexity remains O(n) time and O(1) space.
Both strategies rely on the same observation: more than one decreasing pair makes the array impossible to fix with a single modification. Detecting violations early allows you to terminate quickly when the limit is exceeded.
Recommended for interviews: The single-pass greedy solution is the expected answer. It shows you can reason about array ordering and handle edge cases like [3,4,2,3] where modifying the wrong element breaks earlier order. Interviewers typically want to see a linear scan with constant space, careful boundary checks, and clear reasoning about when to adjust the previous value versus the current one. Mentioning the relationship to common greedy decision-making patterns helps demonstrate deeper understanding.
Approach 1: Single Pass Approach
This approach makes a single pass through the array while keeping a count of occurrences where nums[i] > nums[i+1]. If more than one such occurrence is found, it returns false. During the traversal, if such an occurrence is found, we will attempt to resolve it by modifying nums[i] or nums[i+1] optimally based on their neighbors.
def checkPossibility(nums):
count = 0
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
count += 1
if count > 1:
return False
if i > 0 and nums[i + 1] < nums[i - 1]:
nums[i + 1] = nums[i]
return Truepublic class Solution {
public boolean checkPossibility(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
count++;
if (count > 1) return false;
if (i > 0 && nums[i + 1] < nums[i - 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] > nums[i + 1]) {
count++;
if (count > 1) return false;
if (i > 0 && nums[i + 1] < nums[i - 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
}
};var checkPossibility = function(nums) {
let count = 0;
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
count++;
if (count > 1) return false;
if (i > 0 && nums[i + 1] < nums[i - 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
};#include <stdbool.h>
bool checkPossibility(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize - 1; i++) {
if (nums[i] > nums[i + 1]) {
count++;
if (count > 1) {
return false;
}
if (i > 0 && nums[i + 1] < nums[i - 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
}public class Solution {
public bool CheckPossibility(int[] nums) {
int count = 0;
for (int i = 0; i < nums.Length - 1; i++) {
if (nums[i] > nums[i + 1]) {
count++;
if (count > 1) return false;
if (i > 0 && nums[i + 1] < nums[i - 1]) {
nums[i + 1] = nums[i];
}
}
}
return true;
}
}The Python solution runs a loop, counting ordinance failures in the array. On the first failure, it optimizes by evaluating the relationship of adjacent elements and making minimal necessary changes.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Two-Pointer Strategy
This approach involves using two pointers to traverse from the start and end of the array. We simulate potential changes to resolve any issues at both ends, using the pointers to converge inwards and analyze changes required to achieve a non-decreasing state.
def checkPossibility(nums):
count = 0
left, right = 0, len(nums) - 1
while left < right:
if nums[left] > nums[left + 1]:
count += 1
if left > 0 and nums[left + 1] < nums[left - 1]:
nums[left + 1] = nums[left]
if nums[right] < nums[right - 1]:
count += 1
if right < len(nums) - 1 and nums[right - 1] > nums[right + 1]:
nums[right - 1] = nums[right]
if count > 1:
return False
left += 1
right -= 1
return Truepublic class Solution {
public boolean checkPossibility(int[] nums) {
int count = 0;
int left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < nums.length - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
}
}#include <vector>
using namespace std;
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
int left = 0, right = nums.size() - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < nums.size() - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
}
};var checkPossibility = function(nums) {
let count = 0;
let left = 0, right = nums.length - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < nums.length - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
};#include <stdbool.h>
bool checkPossibility(int* nums, int numsSize) {
int count = 0;
int left = 0, right = numsSize - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < numsSize - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
}public class Solution {
public bool CheckPossibility(int[] nums) {
int count = 0;
int left = 0, right = nums.Length - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < nums.Length - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
}
}In Python, the two-pointer approach is efficiently implemented to traverse the list and adjust elements. The left and right pointers work in tandem to minimize the number of changes required to keep order.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
function checkPossibility(nums: number[]): boolean {
const isSorted = (nums: number[]) => {
for (let i = 0; i < nums.length - 1; ++i) {
if (nums[i] > nums[i + 1]) {
return false;
}
}
return true;
};
for (let i = 0; i < nums.length - 1; ++i) {
const a = nums[i],
b = nums[i + 1];
if (a > b) {
nums[i] = b;
if (isSorted(nums)) {
return true;
}
nums[i] = a;
nums[i + 1] = a;
return isSorted(nums);
}
}
return true;
}func checkPossibility(nums []int) bool {
isSorted := func(nums []int) bool {
for i, b := range nums[1:] {
if nums[i] > b {
return false
}
}
return true
}
for i := 0; i < len(nums)-1; i++ {
a, b := nums[i], nums[i+1]
if a > b {
nums[i] = b
if isSorted(nums) {
return true
}
nums[i] = a
nums[i+1] = a
return isSorted(nums)
}
}
return true
}Complexity comparison
| Approach | Complexity |
|---|---|
| Single Pass Approach | Time Complexity: O(n) |
| Two-Pointer Strategy | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass Greedy | O(n) | O(1) | Best general solution. Preferred in interviews due to simple linear scan and clear greedy decision. |
| Two-Pointer Strategy | O(n) | O(1) | Useful for reasoning about neighboring elements and local violations in array ordering. |
Frequently asked questions
Is Non-decreasing Array easy or hard?
Non-decreasing Array is considered a Medium difficulty problem. The implementation is short, but the challenge lies in correctly deciding which element to modify when a violation appears and handling edge cases such as early elements in the array.
Non-decreasing Array Python/Java solution
Both Python and Java implementations follow the same greedy logic: iterate once, detect when nums[i] < nums[i-1], and decide which element to modify based on the previous value. The implementation uses constant space and linear time regardless of language.
How to solve Non-decreasing Array in O(n)?
Traverse the array once and track whether a decreasing pair appears. If nums[i] < nums[i-1], increment a violation counter. Fix the issue greedily by adjusting nums[i-1] when nums[i] >= nums[i-2]; otherwise adjust nums[i]. If more than one violation appears, the array cannot be fixed with a single modification.
What is the best approach for Non-decreasing Array?
The optimal solution is a greedy single-pass approach. Iterate through the array and count violations where nums[i] < nums[i-1]. When a violation occurs, adjust either the previous or current element depending on surrounding values. This approach runs in O(n) time with O(1) extra space.
Is Non-decreasing Array asked at Google/Amazon/Meta?
Non-decreasing Array appears in technical interviews that test array reasoning and greedy thinking. Similar variants have been reported at companies like Amazon and Google where candidates must detect ordering violations and reason about minimal modifications.
What data structure is used in Non-decreasing Array?
The problem primarily uses a simple array traversal. No additional data structures are required because the greedy solution only compares adjacent elements and keeps a small counter to track violations.
What is the time complexity of Non-decreasing Array?
The optimal algorithm runs in O(n) time because the array is scanned once. Each comparison checks whether the non-decreasing property is violated. Only constant extra variables are used, so the space complexity is O(1).