Showing posts from August, 2017

Non-decreasing Array, by LeetCode

New problem by LeetCode, right here: Given an array with  n  integers, your task is to check if it could become non-decreasing by modifying  at most   1  element. We define an array is non-decreasing if  array[i] <= array[i + 1]  holds for every  i  (1 <= i < n). Example 1: Input: [4,2,3] Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array. Example 2: Input: [4,2,1] Output: False Explanation: You can't get a non-decreasing array by modify at most one element. Note:  The  n  belongs to [1, 10,000]. The solution that I came up is not the most glamorous one, but beat the majority of the other submissions. Here is the idea: you're going to do one pass thru the array looking to see if it is in "ascending" order (ascending is in quotes because you may have dupes). That's O(n). As you do so check how many "errors" you find w