Vultr DocsLatest Content

Non-decreasing Array

Updated on 07 July, 2025
Non-decreasing Array header image

Problem Statement

Given an integer array named nums that contains n elements, the problem asks us to check whether it is possible to modify at most one element in the array to make it non-decreasing. A non-decreasing array means for every i from 0 to n-2, the condition nums[i] <= nums[i + 1] must hold true. If this condition can be met through zero or one modification, then the function should return true, otherwise false.

Examples

Example 1

Input:

nums = [4,2,3]

Output:

true

Explanation:

You could modify the first 4 to 1 to get a non-decreasing array.

Example 2

Input:

nums = [4,2,1]

Output:

false

Explanation:

You cannot get a non-decreasing array by modifying at most one element.

Constraints

  • n == nums.length
  • 1 <= n <= 104
  • -105 <= nums[i] <= 105

Approach and Intuition

To solve this problem, one can analyze the array for violations of the non-decreasing order rule (i.e., nums[i] > nums[i + 1]). The key intuition is:

  1. Iterate through the array elements and identify spots where nums[i] > nums[i + 1].
  2. If more than one such spot is found, immediately return false, as more than one modification will be needed, which violates the problem constraints.
  3. If no such spot is found, return true since the array is already non-decreasing.
  4. If exactly one violation spot is found, evaluate the impact of modifying either the current element (nums[i]) or the next element (nums[i + 1]) to fix the order:
    • Modify nums[i] to a value less than or equal to nums[i + 1]. This should also satisfy the condition with the previous element nums[i - 1] if exists.
    • Modify nums[i + 1] to a value greater than or equal to nums[i]. This should maintain the condition with nums[i + 2] if exists.
  5. If either modification strategy works without causing new violations, return true.
  6. If neither modification is feasible without causing additional violations, return false.

Here's how the intuitive steps map with the provided examples:

  • Example 1:

    • Array: [4, 2, 3]
    • Only one violating spot (4 > 2).
    • Modifying the first 4 to 1 corrects the violation and no further violations are introduced.
    • Result is true.

  • Example 2:

    • Array: [4, 2, 1]
    • Two violating spots (4 > 2 and 2 > 1).
    • This requires at least two modifications to correct, hence, it's impossible with the given constraints.
    • Result is false.

The approach leverages the idea of scanning for the minimal incorrect pattern and attempting localized corrections, which aligns with the constraints of minimal change for a valid answer.

Solutions

  • Java
java 
class Solution {
    public boolean canModifyArray(int[] arr) {
            
        int violations = 0;
        for (int j = 1; j < arr.length; j++) {
                
            if (arr[j - 1] > arr[j]) {
                    
                if (violations == 1) {
                    return false;
                }
                    
                violations++;
                    
                if (j < 2 || arr[j - 2] <= arr[j]) {
                    arr[j - 1] = arr[j];
                } else {
                    arr[j] = arr[j - 1];
                }
            }
        }
            
        return true;
    }
}

This Java program implements a method canModifyArray to determine if it's possible to make an array non-decreasing by modifying at most one element. The method iterates through the array, checking if the current element is less than the previous one, which is considered a violation of the non-decreasing order.

  • Initialize a counter violations to zero. This counts how many times the array's order is violated.
  • Loop through the array starting from the second element. If the current element is less than the previous one:
    • Check if already one modification has occurred (violations equals 1); if yes, return false.
    • Increment the violations counter.
    • If the position is beyond the second element (j >= 2) and the element two positions back is less than or equal to the current element, adjust the previous element (arr[j - 1]) to the current (arr[j]).
    • Otherwise, adjust the current element (arr[j]) to the previous one (arr[j - 1]).
  • After completing the loop, if no more than one violation was detected or appropriately corrected, return true, indicating that the array can be adjusted to maintain or achieve a non-decreasing order with at most one modification.

In essence, this approach utilizes a greedy algorithm strategy, optimizing the array iteratively to ensure it can become or remain non-decreasing with minimum changes.

  • Python
python 
class Solution:
    def canBeNonDecreasing(self, arr: List[int]) -> bool:
            
        violations = 0
        for index in range(1, len(arr)):
                
            if arr[index - 1] > arr[index]:
                    
                if violations == 1:
                    return False
                    
                violations += 1
                    
                if index < 2 or arr[index - 2] <= arr[index]:
                    arr[index - 1] = arr[index]
                else:
                    arr[index] = arr[index - 1]
                        
        return True

Explore a Python solution to determine if an array can be modified into a non-decreasing array by changing at most one element. The canBeNonDecreasing method analyzes the array by counting instances where the current element is less than its predecessor—which are termed violations. Here's the approach followed in the implementation:

  • Initialize a counter for violations (violations) set to zero.
  • Traverse the array from the second element and compare each with the prior.
  • If a violation is found:
    • If there's already one violation recorded, return False as more than one modification would be required.
    • Increment the violation counter.
    • Check elements further back to apply the optimal modification (adjusting either the current or previous element in the array) without introducing new violations.
  • Return True if the end of the array is reached with one or zero violations, indicating that it can be modified to non-decreasing with at most one change.

Use this strategy to efficiently check and handle arrays by only adjusting when necessary while keeping a minimal count of modifications.

Comments

No comments yet.