Non-decreasing Array, by LeetCode
New problem by LeetCode, right here: https://leetcode.com/problems/non-decreasing-array/description/
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 where an error is A[i] > A[i+1]. If you find more than one of those errors, you can bail, it is a Nay in such a case. But if you find only one, well, you want to see if there is a way to fix it. There are only two options here:
- Either setting A[i] to be the same as A[i+1] will do it (another check here: O(n))
- Or setting A[i+1] to be the same as A[i] will do it (another check here: O(n))
Hence, a total of O(3n), or a max of 30,000 iterations. Code is down below, cheers, Marcelo.
public class Solution
{
public bool CheckPossibility(int[] nums)
{
int instances = 0;
for (int i = 0; i < nums.Length - 1; i++)
{
if (nums[i] > nums[i + 1])
{
instances++;
if (instances > 1) return false;
//Check both sides
bool oneSideWorks = false;
int temp = nums[i];
nums[i] = nums[i + 1];
if (IsSorted(nums)) oneSideWorks = true;
nums[i] = temp;
if (!oneSideWorks)
{
temp = nums[i + 1];
nums[i + 1] = nums[i];
if (IsSorted(nums)) oneSideWorks = true;
nums[i + 1] = temp;
}
if (!oneSideWorks) return false;
}
}
return true;
}
private bool IsSorted(int[] nums)
{
for (int i = 0; i < nums.Length - 1; i++)
{
if (nums[i] > nums[i + 1]) return false;
}
return true;
}
}
Well done, Marcelo! I'm usually lazy to spend much time working on an elegant solution for easy problems, so my solution is not elegant at all:
ReplyDeleteclass Solution {
private:
bool movingSourceToDestinationHelps(vector& nums, int i, int src, int dest) {
int old_value = nums[dest];
nums[dest] = nums[src];
bool helps = nonDecreasing(nums, i > 0 ? i - 1 : i);
nums[dest] = old_value;
return helps;
}
bool nonDecreasing(const vector& nums, int start) {
for (int i = start; i < nums.size() - 1; ++i) {
if (nums[i] > nums[i+1]) return false;
}
return true;
}
public:
bool checkPossibility(vector& nums) {
for (int i = 0; i < nums.size() - 1; ++i) {
if (nums[i] <= nums[i+1]) continue;
return movingSourceToDestinationHelps(nums, i, i, i + 1) || movingSourceToDestinationHelps(nums, i, i + 1, i);
}
return true;
}
};
Have a splendid weekend!
Cheers,
Taras