NeetCode #129LC-665MediumArrays & Hashing
← Back to All Problems#129 · #665 · Non-decreasing Array(非递减数列)
📌 Problem Statement & Constraints
Given an array
nums, return true if it can become non-decreasing by modifying at most one element. Constraints: 1 <= nums.length <= 10^4, -10^5 <= nums[i] <= 10^5.💡 Core Algorithmic Approaches
- Scan for descents: a position where
nums[i-1] > nums[i]. More than one such position means the answer isfalse. - At a single descent, two repairs are possible: lower
nums[i-1]tonums[i], or raisenums[i]tonums[i-1]. - The choice is forced by the element before the descent: if
nums[i-2] <= nums[i], loweringnums[i-1]works; otherwise raisingnums[i]is required. - When
i == 1there is nonums[i-2], so loweringnums[i-1]is always safe -- this is the boundary case that trips most implementations.
💻 Benchmark Python3 Implementation
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
violations = 0
for i in range(1, len(nums)):
if nums[i - 1] > nums[i]:
violations += 1
if violations > 1:
return False # more than one descent
# choose the repair that keeps the prefix non-decreasing
if i < 2 or nums[i - 2] <= nums[i]:
nums[i - 1] = nums[i] # lower the left element
else:
nums[i] = nums[i - 1] # raise the right element
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1) extra (the input is modified in place, which is acceptable; copy it if that is undesirable).
⚠️ Interview Pitfalls & Follow-ups
- Always lowering
nums[i-1]:[3, 4, 2, 3]needsnums[2]raised to 4 instead, becausenums[0] = 3 > nums[2] = 2. Thenums[i-2] <= nums[i]test decides. - Forgetting the
i < 2guard: ati == 1there is nonums[i-2], and indexingnums[-1]in Python silently wraps to the last element, producing a wrong decision. - Counting descents without simulating the repair: a repair can resolve or expose later descents, so the count alone is not a valid test.
[4, 2, 3]has one descent and is fixable;[4, 5, 2, 3]also has exactly one descent but is not fixable with a single change, which is why the repair must be applied as you go. - Requiring a strictly increasing result: the requirement is non-decreasing, so equal neighbours are allowed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.