How hard is LeetCode 665. Non-decreasing Array?

LeetCode 665. Non-decreasing Array is rated Medium on LeetCode.

What topics does LeetCode 665. Non-decreasing Array cover?

LeetCode 665. Non-decreasing Array is tagged Array on LeetCode.

Non-decreasing Array — LeetCode 665 Python Solution

MediumArray

Problem: #665
Reading time: 3 min
Source: leetcode.com

The problem

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

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

Python solution

Python

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        def is_sorted(nums: List[int]) -> bool:
            return all(a <= b for a, b in pairwise(nums))

        n = len(nums)
        for i in range(n - 1):
            a, b = nums[i], nums[i + 1]
            if a > b:
                nums[i] = b
                if is_sorted(nums):
                    return True
                nums[i] = nums[i + 1] = a
                return is_sorted(nums)
        return True

Complexity

Measure	Complexity
Time	O(n)
Space	O(1) to O(n) auxiliary

Frequently asked questions

How hard is LeetCode 665. Non-decreasing Array?: LeetCode 665. Non-decreasing Array is rated Medium on LeetCode.
What topics does LeetCode 665. Non-decreasing Array cover?: LeetCode 665. Non-decreasing Array is tagged Array on LeetCode.