Non-decreasing Array - Solution & Explanation
Problem Statement
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.
The C solution uses a single loop to traverse the array and a counter to track violations of the non-decreasing order. If a violation is found and it's the first one, the program attempts to adjust the values strategically by evaluating neighbors.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since no additional space is used dependent on input size.
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.
This C solution utilizes a two-pointer method to inspect boundary conditions, adjusting wrong elements while ensuring the count of such modifications doesn't exceed one. Left and right pointers indicate positions to examine simultaneously.
Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Single Pass Approach | Time Complexity: O(n), where n is the length of the array. |
| Two-Pointer Strategy | Time Complexity: O(n) |
| Default Approach | — |
Detailed 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. |
Video Solution
Non-Decreasing Array - Leetcode 665 - Python • NeetCode • 68,269 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Non-decreasing Array easy or hard?
Non-decreasing Array Python/Java solution
How to solve Non-decreasing Array in O(n)?
What is the best approach for Non-decreasing Array?
Is Non-decreasing Array asked at Google/Amazon/Meta?
What data structure is used in Non-decreasing Array?
What is the time complexity of Non-decreasing Array?
Ready to solve this problem?
Practice Non-decreasing Array with our built-in code editor and test cases.
Practice on FleetCode