We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Non-decreasing Array

Difficulty: Medium

Problem Description

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).

Key Insights

  • An array is non-decreasing if for every adjacent pair of elements, the first is less than or equal to the second.
  • We can allow at most one modification to achieve a non-decreasing condition.
  • When a violation occurs (i.e., nums[i] > nums[i + 1]), we have to decide which element to modify.
  • Modifying either nums[i] or nums[i + 1] should not create a new violation with adjacent elements.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we will iterate through the array while checking for violations of the non-decreasing condition. When we encounter a violation (nums[i] > nums[i + 1]), we will check whether we can fix it by either modifying nums[i] or nums[i + 1]. If we can fix the violation without creating a new one, we continue; otherwise, we return false. We keep track of whether we've already made a modification.

Code Solutions

def checkPossibility(nums):
    count = 0  # To count the number of modifications
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            count += 1
            if count > 1:  # More than one modification needed
                return False
            # Modify nums[i] or nums[i + 1]
            if i > 0 and nums[i - 1] > nums[i + 1]:
                nums[i + 1] = nums[i]  # Modify nums[i + 1]
    return True
← Back to All Questions