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.length1 <= n <= 104-105 <= nums[i] <= 105The key idea in #665 Non-decreasing Array is to determine whether the array can become non-decreasing by modifying at most one element. A non-decreasing array means every element satisfies nums[i] <= nums[i+1]. While scanning the array, we look for violations where this condition fails.
A practical approach is to perform a single pass through the array and count how many times a decreasing pair appears. If more than one violation occurs, it is impossible to fix the array with just one modification. When a violation is found, we conceptually decide whether adjusting the current element or the previous element would maintain the non-decreasing property for the remaining array.
This method relies on a greedy decision using nearby elements to keep the array valid without breaking earlier order. Because the array is scanned only once and modifications are simulated rather than fully applied, the approach runs efficiently in linear time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Single Pass Check | O(n) | O(1) |
| Brute Force Modification Check | O(n^2) | O(1) |
NeetCode
This approach makes a single pass through the array while keeping a count of occurrences where nums[i] > nums[i+1]. If more than one such occurrence is found, it returns false. During the traversal, if such an occurrence is found, we will attempt to resolve it by modifying nums[i] or nums[i+1] optimally based on their neighbors.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since no additional space is used dependent on input size.
1#include <stdbool.h>
2
3bool checkPossibility(int* nums, int numsSize) {
4 int count = 0;
5 for (intThe C solution uses a single loop to traverse the array and a counter to track violations of the non-decreasing order. If a violation is found and it's the first one, the program attempts to adjust the values strategically by evaluating neighbors.
This approach involves using two pointers to traverse from the start and end of the array. We simulate potential changes to resolve any issues at both ends, using the pointers to converge inwards and analyze changes required to achieve a non-decreasing state.
Time Complexity: O(n)
Space Complexity: O(1)
1#include
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of array validation and greedy decision-making problem is common in technical interviews. It tests understanding of edge cases, array traversal, and how to make optimal local decisions.
The optimal approach uses a greedy single-pass scan of the array. Whenever a decreasing pair is detected, we decide whether modifying the current element or the previous one would maintain the non-decreasing property while ensuring only one modification is allowed.
A greedy strategy works because the decision at each violation only depends on nearby elements. By adjusting the current or previous value conceptually, we can maintain the non-decreasing condition without affecting earlier validated elements.
The problem can be solved using just the input array without any additional data structures. A simple iteration with constant variables to track violations is sufficient, making the solution space-efficient.
This C solution utilizes a two-pointer method to inspect boundary conditions, adjusting wrong elements while ensuring the count of such modifications doesn't exceed one. Left and right pointers indicate positions to examine simultaneously.