# 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.

• This post is deleted!

• @nullpointerP can you exmplin please, why example [1,5,8,3] is true. How does it becomes [1,3,5,8] with one swap?
Actually the same problem is with [3,2,1] . Here the answer should be true, because [3,2,1] becomes [1,2,3] with 1 swap

• 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;

}
``````

• @elmirap I am sorry I entered the wrong result. I have already modified it. Thanks!

• @nullpointerP welcome

• ``````def check_one_swap(s):
n = len(s)
first = second = -1
if n == 1:
return true
for i in range(n-1):
if s[i+1] >= s[i]:
continue
else:
if first == -1:
first = i
second = i + 1
elif second == first + 1:
second = i + 1
else:
return false
return s[first] >= s[second - 1] and s[second] <= s[first + 1] and (True if first == 0 else s[second] >= s[first - 1]) and (True if second == n -1 else s[first] <= s[second + 1])
``````

• @elmirap
int res = Arrays.binarySearch(nums, nums[swaps[0] + 1]);
if (res < 0) {
res = -res;
res -= 1;
} else
res += 1;
In this code block, how can res be negative? since you are searching for an element in the array.

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