Scale Engineer

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 <= 104
  • -105 <= nums[i] <= 105

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

  1. Define a helper function isSorted(arr) that checks if an array is non-decreasing in O(N) time.
  2. Check if the input array nums is already sorted using the helper function. If it is, return true as zero modifications are needed.
  3. Iterate through the array with an index i from 0 to n-1.
  4. 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].
  5. Check if this temp array is sorted using the isSorted helper function.
  6. 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.
  7. 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.

class Solution {    public boolean checkPossibility(int[] nums) {        // Check the case where the array is already sorted (0 modifications)        if (isSorted(nums, -1)) {            return true;        }         // Try modifying at each position        for (int i = 0; i < nums.length; i++) {            // Check if the array becomes sorted if we ignore the element at index i            if (isSorted(nums, i)) {                return true;            }        }         return false;    }     // Helper function to check if an array is sorted, ignoring one index    private boolean isSorted(int[] nums, int skipIndex) {        int prev = Integer.MIN_VALUE;        for (int i = 0; i < nums.length; i++) {            if (i == skipIndex) {                continue;            }            if (nums[i] < prev) {                return false;            }            prev = nums[i];        }        return true;    }}

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.

Solutions

class Solution {public  boolean checkPossibility(int[] nums) {    for (int i = 0; i < nums.length - 1; ++i) {      int a = nums[i], b = nums[i + 1];      if (a > b) {        nums[i] = b;        if (isSorted(nums)) {          return true;        }        nums[i] = a;        nums[i + 1] = a;        return isSorted(nums);      }    }    return true;  }private  boolean isSorted(int[] nums) {    for (int i = 0; i < nums.length - 1; ++i) {      if (nums[i] > nums[i + 1]) {        return false;      }    }    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 →

Next problem