Two Swaps

Given a permutation of some of the first natural numbers in an array arr[], determine if the array can be sorted in exactly two swaps. A swap can involve the same pair of indices twice.

Return true if it is possible to sort the array with exactly two swaps, otherwise return false.

Examples:

Input: arr = [4, 3, 2, 1]
Output: true
Explanation: First, swap arr[0] and arr[3]. The array becomes [1, 3, 2, 4]. Then, swap arr[1] and arr[2]. The array becomes [1, 2, 3, 4], which is sorted.

Input: arr = [4, 3, 1, 2]
Output: false
Explanation: It is not possible to sort the array with exactly two swaps.

Constraints:
1 ≤ arr.size() ≤ 10⁶
1 ≤ arr[i] ≤ arr.size()

Approach 01:

#include <vector>

class Solution {
public:
    bool checkSorted(const std::vector<int>& array) {
        int arraySize = array.size();
        int mismatchCount = 0;

        // Count mismatches
        for (int i = 0; i < arraySize; ++i) {
            if (array[i] == i + 1)
                continue;
            else
                mismatchCount++;
        }

        // If there are 0 or exactly 3 mismatches
        if (mismatchCount == 0 || mismatchCount == 3)
            return true;

        // Check if it's a swap
        else if (mismatchCount == 4) {
            for (int i = 0; i < arraySize; ++i) {
                if (array[i] != i + 1 && array[array[i] - 1] == i + 1) {
                    mismatchCount--;
                } else if (array[i] == i + 1) {
                    continue;
                } else {
                    return false;
                }
            }
            return mismatchCount == 0;
        }

        return false;
    }
};

class Solution:
    def checkSorted(self, array):
        arraySize = len(array)
        mismatchCount = 0

        # Count mismatches
        for i in range(arraySize):
            if array[i] == i + 1:
                continue
            else:
                mismatchCount += 1

        # If there are 0 or exactly 3 mismatches
        if mismatchCount == 0 or mismatchCount == 3:
            return True

        # Check if it's a swap
        elif mismatchCount == 4:
            for i in range(arraySize):
                if array[i] != i + 1 and array[array[i] - 1] == i + 1:
                    mismatchCount -= 1
                elif array[i] == i + 1:
                    continue
                else:
                    return False
            return mismatchCount == 0

        return False

Time Complexity

• First loop (mismatch count):

  The algorithm iterates through the array of size n once to count mismatches. The time complexity for this operation is \(O(n)\).

• Second loop (swap check, if needed):

  In the worst case, the second loop also iterates through the array once to check if mismatches can be corrected with swaps. This adds another \(O(n)\).

• Overall Time Complexity:

  Since both loops run in \(O(n)\), the overall time complexity is \(O(n)\), where n is the size of the array.

Space Complexity

• Auxiliary Space:

  The algorithm only uses a few extra variables (e.g., mismatchCount, arraySize), and there are no additional data structures that grow with input size.

• Overall Space Complexity:

  The space complexity is \(O(1)\), meaning the algorithm uses constant space.