⚡Flashcard Drill➔
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

  1. Scan for descents: a position where nums[i-1] > nums[i]. More than one such position means the answer is false.
  2. At a single descent, two repairs are possible: lower nums[i-1] to nums[i], or raise nums[i] to nums[i-1].
  3. The choice is forced by the element before the descent: if nums[i-2] <= nums[i], lowering nums[i-1] works; otherwise raising nums[i] is required.
  4. When i == 1 there is no nums[i-2], so lowering nums[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] needs nums[2] raised to 4 instead, because nums[0] = 3 > nums[2] = 2. The nums[i-2] <= nums[i] test decides.
  • Forgetting the i < 2 guard: at i == 1 there is no nums[i-2], and indexing nums[-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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems