Non-decreasing Array

Med

#0619Time: O(N^2), where N is the number of elements in the array. The main loop runs N times, and the helper function `isSorted` also runs in O(N) time, leading to a total complexity of O(N*N).Space: O(1) if the check is done in-place without creating a new array, as shown in the provided snippet. If a new array is created in each iteration, the space complexity would be O(N).1 company

Data structures

Array

Companies

Cashfree

Prompt

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 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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process of modifying each element one by one and checking if the resulting array becomes non-decreasing. If we find any such modification that works, we can conclude it's possible. The simulation is done by effectively removing each element in turn and checking if the remaining elements form a non-decreasing sequence. If they do, it implies the original element could have been changed to a suitable value.

Algorithm

Define a helper function isSorted(arr) that checks if an array is non-decreasing in O(N) time.
Check if the input array nums is already sorted using the helper function. If it is, return true as zero modifications are needed.
Iterate through the array with an index i from 0 to n-1.
In each iteration, simulate the modification of the element nums[i]. A robust way to simulate this is to create a new temporary array temp that contains all elements of nums except for nums[i].
Check if this temp array is sorted using the isSorted helper function.
If temp is sorted, it means that the original array could be made non-decreasing by appropriately changing the value of nums[i]. Therefore, return true.
If the loop completes without finding any such i, it means that modifying any single element is not sufficient. Return false.

Walkthrough

The brute-force strategy systematically checks every possibility. Since we can modify at most one element, we can iterate through each element of the array and consider it as the one to be modified. For each element nums[i], we test if changing its value can make the entire array non-decreasing.

A simple way to perform this test is to temporarily remove nums[i] from the array and check if the remaining n-1 elements are non-decreasing. If they are, it means a 'slot' exists between nums[i-1] and nums[i+1] where nums[i] could be placed, thus making the whole array non-decreasing. For example, if we have [..., 5, 10, 6, ...] and we remove 10, the remaining sequence [..., 5, 6, ...] is locally ordered. This implies we could have changed 10 to a value like 5 or 6 to fix the array.

The algorithm iterates through each index i, creates a temporary array without nums[i], and checks if this temporary array is sorted. If this condition is met for any i, we return true. If the loop finishes without success, it means no single modification can solve the problem, so we return false. This also correctly handles arrays that are already sorted, as removing any element from a sorted array leaves a sorted array.

1class Solution {2    public boolean checkPossibility(int[] nums) {3        // Check the case where the array is already sorted (0 modifications)4        if (isSorted(nums, -1)) {5            return true;6        }7 8        // Try modifying at each position9        for (int i = 0; i < nums.length; i++) {10            // Check if the array becomes sorted if we ignore the element at index i11            if (isSorted(nums, i)) {12                return true;13            }14        }15 16        return false;17    }18 19    // Helper function to check if an array is sorted, ignoring one index20    private boolean isSorted(int[] nums, int skipIndex) {21        int prev = Integer.MIN_VALUE;22        for (int i = 0; i < nums.length; i++) {23            if (i == skipIndex) {24                continue;25            }26            if (nums[i] < prev) {27                return false;28            }29            prev = nums[i];30        }31        return true;32    }33}

Complexity

Time

O(N^2), where N is the number of elements in the array. The main loop runs N times, and the helper function `isSorted` also runs in O(N) time, leading to a total complexity of O(N*N).

Space

O(1) if the check is done in-place without creating a new array, as shown in the provided snippet. If a new array is created in each iteration, the space complexity would be O(N).

Trade-offs

Pros

Simple to understand and implement.
Directly simulates the condition of fixing the array by altering one element.

Cons

Inefficient for large arrays due to its quadratic time complexity.
Creates a new array in every iteration, which can be memory-intensive for large inputs.

This approach iterates through the array just once to find any violation of the non-decreasing property. A violation occurs when nums[i] > nums[i+1]. If more than one such violation is found, it's impossible to fix with one modification. If exactly one violation is found, we need to check if it can be resolved by changing either nums[i] or nums[i+1] without causing a new violation.

Algorithm

Initialize a counter modifications = 0.
Iterate through the array from i = 0 to n-2.
If nums[i] <= nums[i+1], the order is correct, so continue.
If nums[i] > nums[i+1], a violation is found. a. Increment modifications. If modifications becomes greater than 1, return false immediately. b. We must fix this violation. We have two choices: lower nums[i] or raise nums[i+1]. c. Check if lowering nums[i] is a valid move. This is possible if it doesn't create a new violation with nums[i-1]. The condition is i == 0 || nums[i-1] <= nums[i+1]. d. If lowering nums[i] is not possible (the condition in 4c is false), we must attempt to raise nums[i+1]. We do this by setting nums[i+1] = nums[i]. This modification is carried forward for subsequent checks in the loop. e. If lowering nums[i] is possible, we can conceptually proceed as if nums[i] was lowered. We don't need to actually modify the array in this case, as the original nums[i] value won't be used in future comparisons.
If the loop completes, it means we encountered at most one fixable violation. Return true.

Walkthrough

We can solve this problem efficiently in a single pass. The idea is to iterate through the array, keeping track of the number of modifications made. If the array is already non-decreasing, we'll complete the pass without any modifications and return true.

When we encounter the first violation, where nums[i] > nums[i+1], we increment our modification count. If we ever find a second violation, we know it's impossible to fix with just one change, so we can return false immediately.

With the first violation at index i, we must decide whether to lower nums[i] or raise nums[i+1]. Lowering nums[i] is generally preferable because it results in smaller values, which are less likely to conflict with subsequent elements. We can lower nums[i] (e.g., to nums[i+1]) if this change doesn't violate the order with the preceding element, nums[i-1]. This is valid if i == 0 (no preceding element) or if nums[i-1] <= nums[i+1].

If we cannot lower nums[i] (because nums[i-1] > nums[i+1]), our only alternative is to raise nums[i+1] (e.g., to nums[i]). We perform this modification in the array and continue our scan. If this change leads to another violation later on, our modification counter will catch it.

If we finish the loop, it means we have made at most one valid modification, so the array can become non-decreasing. Thus, we return true.

1class Solution {2    public boolean checkPossibility(int[] nums) {3        int modifications = 0;4        for (int i = 0; i < nums.length - 1; i++) {5            if (nums[i] > nums[i + 1]) {6                modifications++;7                if (modifications > 1) {8                    return false;9                }10                11                // We found a dip: nums[i] > nums[i+1].12                // Check if lowering nums[i] is possible.13                // This is possible if there's no element before it (i=0)14                // or if the element before it is smaller than or equal to nums[i+1].15                if (i > 0 && nums[i - 1] > nums[i + 1]) {16                    // Lowering nums[i] is not possible as it would break the order with nums[i-1].17                    // So, we must raise nums[i+1].18                    nums[i + 1] = nums[i];19                } 20                // Else, lowering nums[i] is the preferred option. We can imagine21                // nums[i] is changed to nums[i+1]. We don't need to actually modify22                // nums[i] because it won't be checked again in the loop.23            }24        }25        return true;26    }27}

Complexity

Time

O(N), where N is the number of elements. We iterate through the array only once.

Space

O(1), as we only use a few variables to keep track of the state. The input array is modified in-place in this implementation, but this does not affect the asymptotic space complexity.

Trade-offs

Pros

Highly efficient with linear time complexity.
Space-efficient as it operates with constant extra space.

Cons

The logic can be subtle and tricky to get right, especially the conditions for deciding which element to modify.

Solutions

Solution

1class Solution {2public3  boolean checkPossibility(int[] nums) {4    for (int i = 0; i < nums.length - 1; ++i) {5      int a = nums[i], b = nums[i + 1];6      if (a > b) {7        nums[i] = b;8        if (isSorted(nums)) {9          return true;10        }11        nums[i] = a;12        nums[i + 1] = a;13        return isSorted(nums);14      }15    }16    return true;17  }18private19  boolean isSorted(int[] nums) {20    for (int i = 0; i < nums.length - 1; ++i) {21      if (nums[i] > nums[i + 1]) {22        return false;23      }24    }25    return true;26  }27}

1class Solution {2public:3  bool checkPossibility(vector<int> &nums) {4    int n = nums.size();5    for (int i = 0; i < n - 1; ++i) {6      int a = nums[i], b = nums[i + 1];7      if (a > b) {8        nums[i] = b;9        if (is_sorted(nums.begin(), nums.end())) {10          return true;11        }12        nums[i] = a;13        nums[i + 1] = a;14        return is_sorted(nums.begin(), nums.end());15      }16    }17    return true;18  }19};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem