449. Non-decreasing Array
You receive an integer array nums. You are allowed to overwrite at most one element with any integer of your choosing. Decide whether that single edit (or no edit at all) is enough to make the whole array non-decreasing, and return true or false.
An array is non-decreasing when nums[i] <= nums[i + 1] holds for every adjacent pair — equal neighbors are fine.
The function receives the array and returns a boolean.
Example 1:
Input: nums = [4, 2, 3]
Output: true
Explanation: Overwrite the leading 4 with anything <= 2 (say 1) and the array becomes [1, 2, 3], which is non-decreasing.
Example 2:
Input: nums = [3, 4, 2, 3]
Output: false
Explanation: The only dip is 4 > 2, but neither repair works: lowering the 4 collides with the 3 before it, and raising the 2 to 4 creates a new dip against the final 3. No single overwrite fixes it.
Constraints:
- 1 ≤ nums.length ≤ 10⁴
- -10⁵ ≤ nums[i] ≤ 10⁵
Hints:
Scan for a dip — an index where nums[i - 1] > nums[i]. Two or more dips can never be repaired with one edit. With exactly one dip, the interesting question is which side of it to change.
At a dip, prefer lowering the left value to nums[i] — it keeps the ceiling for future elements as low as possible. That is only legal when nums[i - 2] <= nums[i] (or i < 2); otherwise you must raise nums[i] up to nums[i - 1] instead.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 2, 3]
Expected output: true