user1950349 user1950349 - 2 years ago 1814
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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download