What's wrong with my code? - How to know if an array can be sorted by doing only one swap?

Question

I believe that my code is working fine but it failed a few test cases. I don't see the problem.

I'm given a non empty array of integer. I should only need a single swap operation in the array. In other words, I need to check if an array can be sorted into a non-decreasing order by performing only one swap operation.

for example: [1, 3, 5, 3, 7] answer is: true

Asumming that: N is an integer within the range [1..100,000]; each element of array A is an integer within the range [1..1,000,000,000]. Complexity: expected worst-case time complexity is O(N*log(N));

function solution(A) {
  var N = A.length;
  var cnt = 0;
  var B = A.slice();
  B.sort();

  for (var i = 0; i < N; i++) {
    if(A[i] != B[i]) {
      cnt++;
    }
  }

  return  (cnt < 3);
}

is it not working?

Answer 1

Appreciate that the worst case performance for mergesort is O(N*lgN). So if it were possible to answer your question by doing a single mergesort, then we would have an acceptable solution. Consider sorting your array by mergesort and then comparing the original and sorted arrays side-by-side:

original | sorted
7        | 7
3        | 5
5        | 3
3        | 3
1        | 1

Now just walk across both arrays and count the number of items that do not match. If you find more than 2 items, then it implies that a single swap, which involved two items, could not rectify the ordering.

You can sort of rephrase your question as asking how many elements are out of place from a sorted version of the array. If only one swap is needed to achieve a sorted state, then it means there are only two items out of place.