Sponsored
Sponsored
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 <vector>
2using namespace std;
3
4class Solution {
5public:
6 bool checkPossibility(vector<int>& nums) {
7 int count = 0;
8 for (int i = 0; i < nums.size() - 1; ++i) {
9 if (nums[i] > nums[i + 1]) {
10 count++;
11 if (count > 1) return false;
12 if (i > 0 && nums[i + 1] < nums[i - 1]) {
13 nums[i + 1] = nums[i];
14 }
15 }
16 }
17 return true;
18 }
19};The C++ solution similarly implements a single pass with a count for order violations. When a violation is detected and is the only one, an adjustment is made based on neighbors' values to ensure non-decreasing order without further violations.
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)
1public class Solution {
public bool CheckPossibility(int[] nums) {
int count = 0;
int left = 0, right = nums.Length - 1;
while (left < right) {
if (nums[left] > nums[left + 1]) {
count++;
if (left > 0 && nums[left + 1] < nums[left - 1]) {
nums[left + 1] = nums[left];
}
}
if (nums[right] < nums[right - 1]) {
count++;
if (right < nums.Length - 1 && nums[right - 1] > nums[right + 1]) {
nums[right - 1] = nums[right];
}
}
if (count > 1) return false;
left++;
right--;
}
return true;
}
}The C# implementation of the two-pointer technique effectively decreases errors in a non-decreasing sequence by evaluating and modifying both ends of the array while counting adjustments.