# JAVA solution with explanation, O(n) time ~22ms

• To solve the problem we have two cases to keep in mind:

1. Peak is the very first element. E.g. {4, 2, 3} - we can substitute 4(peak element) with value 2 then sequence turns to increasing {2, 2, 3}. For that case we don’t have to override it, assumption is enough.
2. Peak is in the middle. E.g. {3, 4, 2, 3} - we substitute element 4(peak) with value 2 {3, 2, 2, 3} the sequence still has a peak at the beginning. To eliminate this case we have to do extra check with the previous element. We do it with next condition check: "if ((i > 1) && (nums[i] < nums[i-2]))”

In both cases we increment the “count" variable, that stores all peaks that we found traversing the array.
The algorithm has O(n) time complexity and O(1) space complexity.

``````public boolean checkPossibility(int[] nums) {
int count = 0;
// we exit the loop if number of peaks exceeded 1
for (int i = 1; i < nums.length && count <= 1; i++) {
if(nums[i] < nums[i - 1]) {
if ((i > 1) && (nums[i] < nums[i - 2])) {
nums[i] = nums[i - 1];
}
count++;
}
}
return count <= 1;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.