user1950349 user1950349 - 1 year ago 1614
Java Question

How to know if an array can be sorted by one swap or less?

Given an array with n elements, can we sort this array in ascending order by performing only one swap operation?

For example for below array:

int[] data = {1 , 9 , 6, 3}

We need to swap only 9 with 3 and that's only one swap operation by which my array can be in ascending order. If the array is already sorted in ascending order, then we can return true directly.

I started off below code but I am stuck and I am not sure how should I proceed?

public static boolean verifyOrder(int[] data) {
List<Integer> input = new ArrayList<Integer>();
for (int index = 0; index < data.length; index++) {
int j = 0;
while (j < input.size() - 1 && input.get(j) <= input.get(j + 1)) {
if (j == input.size() - 1) {
// yes we can sort array with only one swap operation
return true;

// not sure how should I proceed?

What is the efficient way to deal with this problem?

Answer Source

I'll give you some hints :

  1. You have to iterate over the array exactly once to verify it is already ordered (i.e. check that data[i]<=data[i+1] for each i from 0 to data.length-2).

  2. If during this single iteration you find that data[i]>data[i+1] for some i, you know that data[i] is in the wrong place. If it's possible to do a single swap that will make the array ordered, you need to swap data[i] with something. In order to find which element to swap data[i] with, search for the smallest data[j] where j>i. After swapping data[i] with data[j], you can iterate once more over the array to verify it is ordered.

At most you'll iterate twice over the array, which will give you O(n) running time.