Two Swaps

JavaView on GFG

Problem Overview

Check if array can be sorted with at most two swaps.

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?