LeetCode 665 - Non-decreasing Array
The problem asks whether it is possible to transform a given integer array into a non-decreasing array by modifying at most one element. A non-decreasing array means that every element is less than or equal to the element that comes after it.
Difficulty: 🟡 Medium
Topics: Array
Solution
Problem Understanding
The problem asks whether it is possible to transform a given integer array into a non-decreasing array by modifying at most one element.
A non-decreasing array means that every element is less than or equal to the element that comes after it. Formally, for every valid index i, the condition nums[i] <= nums[i + 1] must hold.
The input is an array nums containing n integers. We are allowed to change the value of at most one element to any integer we want. The goal is to determine whether such a modification can make the entire array non-decreasing.
For example, consider the array [4,2,3]. The problem can be fixed by changing the first element from 4 to 1, producing [1,2,3], which is non-decreasing. However, the array [4,2,1] cannot be fixed with only one modification because there are multiple decreasing relationships.
The constraints are important:
- The array length can be up to
10^4 - Values can range from
-10^5to10^5
An O(n^2) solution would still technically pass for 10^4 in some languages, but it is inefficient and unnecessary. The problem is designed for a linear-time greedy solution.
Several edge cases are important:
- Arrays of length
1are always valid because there are no adjacent comparisons. - Arrays that are already non-decreasing should immediately return
true. - Violations near the beginning or end of the array require careful handling.
- Arrays with duplicate values must still count as non-decreasing because equality is allowed.
- Some arrays contain exactly one inversion, but modifying either side incorrectly can create a new violation.
A naive implementation often fails because fixing one decreasing pair can accidentally break another part of the array.
Approaches
Brute Force Approach
The brute-force strategy tries every possible single modification.
For each index in the array, we pretend to modify that element into every potentially useful value and then check whether the array becomes non-decreasing. Since values are unrestricted, a practical brute-force implementation usually tries replacing elements with neighboring values that could resolve violations.
Another brute-force variation is to test removing the effect of each inversion individually by creating modified copies of the array and validating them.
This approach is correct because it explicitly explores all possible single-element fixes. However, it is inefficient because every attempted modification requires scanning the array again to verify validity.
The repeated rescanning leads to quadratic time complexity.
Optimal Greedy Approach
The key observation is that a non-decreasing array can contain at most one violation if it is fixable with one modification.
A violation occurs when:
nums[i] > nums[i + 1]
When we encounter such a pair, we must decide which element to modify:
- Lower
nums[i] - Raise
nums[i + 1]
The important insight is that we can determine the correct choice locally by looking one step backward.
If nums[i - 1] <= nums[i + 1], then lowering nums[i] is safe.
Otherwise, we must raise nums[i + 1].
This greedy decision works because we only care about preserving the already-processed prefix while eliminating the current violation.
Once we encounter more than one violation, the answer must be false.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) or O(n) | Try fixing each position and recheck the array |
| Optimal | O(n) | O(1) | Greedily repair at most one violation during a single pass |
Algorithm Walkthrough
- Start scanning the array from left to right.
We compare every adjacent pair nums[i] and nums[i + 1] to detect violations of the non-decreasing condition.
2. Keep a counter for violations.
Every time we find nums[i] > nums[i + 1], we increment the counter. If the counter exceeds 1, we immediately return false because more than one modification would be required.
3. Decide which element to modify.
When a violation is found, we must repair it in the safest possible way.
Suppose we detect:
nums[i] > nums[i + 1]
We examine the previous element:
- If
i == 0, there is no previous element, so loweringnums[i]is always safe. - If
nums[i - 1] <= nums[i + 1], we lowernums[i]tonums[i + 1]. - Otherwise, we raise
nums[i + 1]tonums[i].
- Continue scanning after the modification.
The array is updated in-place so future comparisons see the repaired version.
5. Return true if no more than one violation was found.
Why it works
The algorithm maintains the invariant that the prefix processed so far is always non-decreasing after at most one modification.
Whenever a violation appears, the greedy repair minimizes disruption to earlier elements. Lowering the left element is preferred when it preserves the ordering with the previous element. Otherwise, raising the right element is necessary.
Since every violation requires at least one modification, encountering more than one violation proves that the array cannot be fixed with only one change.
Python Solution
from typing import List
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
violations = 0
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
violations += 1
if violations > 1:
return False
if i == 0 or nums[i - 1] <= nums[i + 1]:
nums[i] = nums[i + 1]
else:
nums[i + 1] = nums[i]
return True
The implementation begins by initializing a counter called violations. This tracks how many decreasing pairs have been found.
The loop scans adjacent elements from left to right. Whenever nums[i] > nums[i + 1], the array violates the non-decreasing requirement.
If more than one violation occurs, the function immediately returns False because one modification cannot repair multiple independent problems.
The repair logic is the core of the algorithm. If the previous element does not conflict with nums[i + 1], we lower nums[i]. Otherwise, we raise nums[i + 1].
The array is modified in place so that future comparisons use the corrected values. This allows the algorithm to operate in constant extra space.
If the scan completes with at most one violation, the function returns True.
Go Solution
func checkPossibility(nums []int) bool {
violations := 0
for i := 0; i < len(nums)-1; i++ {
if nums[i] > nums[i+1] {
violations++
if violations > 1 {
return false
}
if i == 0 || nums[i-1] <= nums[i+1] {
nums[i] = nums[i+1]
} else {
nums[i+1] = nums[i]
}
}
}
return true
}
The Go implementation follows the same greedy strategy as the Python solution.
Slices in Go are mutable references to underlying arrays, so modifications happen in place naturally. No additional memory allocation is required.
Integer overflow is not a concern because the algorithm only performs comparisons and assignments, not arithmetic operations.
An empty or single-element slice automatically returns true because the loop never finds a violation.
Worked Examples
Example 1
Input:
nums = [4,2,3]
Initial state:
| i | nums[i] | nums[i+1] | Violation? | Action | Array State |
|---|---|---|---|---|---|
| 0 | 4 | 2 | Yes | Lower nums[0] to 2 | [2,2,3] |
| 1 | 2 | 3 | No | None | [2,2,3] |
Final result:
true
Explanation:
At index 0, the condition 4 > 2 violates non-decreasing order. Since this is the first element, lowering it is safe. The array becomes [2,2,3], which is valid.
Example 2
Input:
nums = [4,2,1]
Initial state:
| i | nums[i] | nums[i+1] | Violation? | Action | Array State |
|---|---|---|---|---|---|
| 0 | 4 | 2 | Yes | Lower nums[0] to 2 | [2,2,1] |
| 1 | 2 | 1 | Yes | Second violation found | Return false |
Final result:
false
Explanation:
The first violation can be repaired, but another decreasing pair remains. Since two fixes would be required, the answer is false.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | The array is scanned once from left to right |
| Space | O(1) | Only a few variables are used regardless of input size |
The algorithm performs a single pass through the array, making one comparison per adjacent pair. Each element is processed a constant number of times, so the runtime is linear.
No auxiliary data structures are used. All modifications occur directly inside the input array, so the extra space usage remains constant.
Test Cases
from typing import List
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
violations = 0
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
violations += 1
if violations > 1:
return False
if i == 0 or nums[i - 1] <= nums[i + 1]:
nums[i] = nums[i + 1]
else:
nums[i + 1] = nums[i]
return True
solution = Solution()
assert solution.checkPossibility([4,2,3]) == True # provided example, one fix works
assert solution.checkPossibility([4,2,1]) == False # provided example, needs two fixes
assert solution.checkPossibility([1,2,3,4]) == True # already non-decreasing
assert solution.checkPossibility([1]) == True # single element
assert solution.checkPossibility([3,4,2,3]) == False # tricky case requiring two fixes
assert solution.checkPossibility([5,7,1,8]) == True # modify middle value
assert solution.checkPossibility([1,5,4,6,7]) == True # one internal violation
assert solution.checkPossibility([10,5,7]) == True # modify first element
assert solution.checkPossibility([1,2,5,3,5]) == True # modify one middle element
assert solution.checkPossibility([1,2,3,2,2]) == False # multiple cascading violations
assert solution.checkPossibility([-1,4,2,3]) == True # negative numbers included
assert solution.checkPossibility([2,2,2]) == True # duplicates allowed
| Test | Why |
|---|---|
[4,2,3] |
Basic successful repair |
[4,2,1] |
Requires more than one modification |
[1,2,3,4] |
Already valid array |
[1] |
Smallest valid input |
[3,4,2,3] |
Classic tricky failure case |
[5,7,1,8] |
Repair in the middle |
[1,5,4,6,7] |
Single inversion |
[10,5,7] |
Repair involving first element |
[1,2,5,3,5] |
Internal repair without breaking prefix |
[1,2,3,2,2] |
Multiple violations after repair |
[-1,4,2,3] |
Negative values |
[2,2,2] |
Equality is allowed |
Edge Cases
One important edge case occurs when the violation appears at the beginning of the array. For example, [4,2,3] has no previous element before 4. A careless implementation might attempt to access nums[-1] or apply the normal logic incorrectly. The implementation handles this explicitly with the condition i == 0, allowing the first element to be safely lowered.
Another tricky case occurs when lowering the left element would create a new violation with the previous value. Consider [3,4,2,3]. If we lower 4 to 2, the array becomes [3,2,2,3], which is still invalid because 3 > 2. The algorithm avoids this by checking whether nums[i - 1] <= nums[i + 1]. If not, it raises the right element instead.
Arrays with duplicate values are another source of subtle bugs. Some implementations mistakenly enforce strictly increasing order rather than non-decreasing order. For example, [2,2,2] should return true. The implementation correctly uses the condition > instead of >=, allowing equal adjacent values.
A final edge case involves multiple distant violations. For example, [5,1,4,2] contains two separate decreasing pairs. A naive greedy algorithm might repair the first issue and incorrectly assume success. This implementation tracks the total number of violations and immediately returns false once the count exceeds one.`