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] <= 105This 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.
The 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.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Single Pass Approach | Time Complexity: O(n), where n is the length of the array. |
| Two-Pointer Strategy | Time Complexity: O(n) |
Non-Decreasing Array - Leetcode 665 - Python • NeetCode • 60,253 views views
Watch 9 more video solutions →Practice Non-decreasing Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor