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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Non-decreasing Array

Number: 665

Difficulty: Medium

Paid? No

Companies: Cashfree, Walmart Labs, Google

Problem Description

Given an array of n integers, determine whether the array can become non-decreasing by modifying at most one element. An array is non-decreasing if for every index i (0-based) such that 0 <= i < n - 1, the condition nums[i] <= nums[i+1] holds.

Key Insights

  • Only one modification is allowed, so you must carefully check for any violations of the non-decreasing order.
  • When a violation (nums[i] < nums[i-1]) is found, decide which element to modify (either nums[i-1] or nums[i]) so that the overall ordering can be maintained.
  • If more than one violation is encountered, it isn’t possible to achieve the non-decreasing order with just one change.
  • Handling edge cases (e.g., when the violation is at the beginning of the array) is crucial.

Space and Time Complexity

Time Complexity: O(n) - A single linear scan through the array. Space Complexity: O(1) - Modifications and counters are done in-place without extra space.

Solution

The main idea is to iterate through the array and count the number of violations where a current element is less than its previous element. If more than one violation is found, return false. At the time of the violation, decide whether to adjust the previous element (nums[i-1]) or the current element (nums[i]):

  1. If the violation is at the beginning of the array (i == 1) or if nums[i] >= nums[i-2], modify the previous element (i.e., set nums[i-1] to nums[i]). This ensures the sequence before the violation remains sorted.
  2. Otherwise, if modifying the previous element would lead to another violation, modify the current element (nums[i]) to the value of the previous element.
  3. Continue the scan; if more than one violation is encountered, it means the array cannot be fixed with a single modification.

This greedy approach ensures that we make the locally optimal change which could eventually lead to a globally non-decreasing array.

Code Solutions

# Python solution for Non-decreasing Array

def checkPossibility(nums):
    # Initialize counter for modifications made
    modifications = 0
    # Loop through the array starting from index 1
    for i in range(1, len(nums)):
        # If current element is less than previous, a violation is detected
        if nums[i] < nums[i - 1]:
            modifications += 1
            # If more than one modification is needed, return False
            if modifications > 1:
                return False
            # Decide whether to adjust nums[i-1] or nums[i]
            if i == 1 or nums[i] >= nums[i - 2]:
                # Modification: lower nums[i-1] to nums[i] 
                nums[i - 1] = nums[i]
            else:
                # Modification: increase nums[i] to nums[i-1]
                nums[i] = nums[i - 1]
    # If we complete scanning with at most one modification, return True
    return True

# Example usage
print(checkPossibility([4, 2, 3]))  # Expected output: True
print(checkPossibility([4, 2, 1]))  # Expected output: False
← Back to All Questions