## Sunday, June 5, 2016

### Non-decreasing array after 1 or less swap

https://discuss.leetcode.com/topic/148/non-decreasing-array-after-1-or-less-swap
A non-empty zero-indexed array A consisting of N integers is given. You can performance 1 or less swap operation in array A. The goal is to check whether array A can be non-decreasing order after 1 or less swap.
Example: [1,5,8,3] => false
[3,2,1] => true
It was from Samsung OA
An implementation. Search for maximum two inversions. Keep the positions at which inversions happens and swap. Then check if array is in ascendng way O(n)

boolean isNonDecreasing(int[] nums) {
if (nums.length <= 1)
return true;
int s =  0;
int cnt = 0;
int[] swaps = new int[2];
while (s < nums.length - 1) {
if (nums[s] > nums[s + 1]) {
if (cnt == 2)
return false;
else {
swaps[cnt] = s;
cnt++;
}
}
s++;
}
if (cnt == 0)
return true;
if (cnt <= 2) {
if (cnt == 1) {
int res = Arrays.binarySearch(nums, nums[swaps[0] + 1]);
if (res < 0) {
res = -res;
res -= 1;
} else
res += 1;
swap(res, swaps[0] + 1, nums);

}
else if (cnt == 2)
swap(swaps[0], swaps[1] + 1, nums);
s = 0;
while (s < nums.length - 1) {
if (nums[s] > nums[s + 1])
return false;
s++;
}
return true;
}
else
return false;

}