Two Swaps

JavaView on GFG

Intuition

Check if array can be sorted with at most two swaps. Identify out-of-place elements and verify.

Algorithm

1Compare array with sorted version. Collect mismatched positions. If 0: done. If 2: verify swap fixes it. If 4: verify two swaps fix it. Else: impossible.

Common Pitfalls

•Count mismatches with sorted array. 0 mismatches: already sorted. 2: one swap. 4: try two swaps. Else: false.

Two Swaps.java

Java

// Approach: Compare array to sorted version. Count positions differing; exactly 0 or 2 mismatches = one swap.
// Time: O(n log n) Space: O(n)
class Solution {

    public boolean checkSorted(List<Integer> arr) {
        int minSwap = 0;
        for (int i = 0; i < arr.size(); i++) {
            while (i + 1 != arr.get(i)) {
                int ind = arr.get(i) - 1;
                int t = arr.get(ind);
                arr.set(ind, arr.get(i));
                arr.set(i, t);
                minSwap++;
            }
        }

        if (minSwap == 0 || minSwap == 2)
            return true;
        return false;
    }
}

Was this solution helpful?