{x}
blog image

Minimum Adjacent Swaps to Make a Valid Array

Solution Explanation: Minimum Adjacent Swaps to Make a Valid Array

This problem asks for the minimum number of adjacent swaps needed to make an array valid. A valid array has its minimum element at the beginning and its maximum element at the end. The solution leverages a greedy approach by focusing on the positions of the minimum and maximum elements.

Algorithm:

  1. Find Indices: Iterate through the array nums to find the indices i and j of the minimum and maximum elements, respectively. The code carefully handles cases where there are multiple minimum or maximum values, choosing the leftmost minimum and rightmost maximum.

  2. Handle Cases:

    • If i == j, the array is already valid (minimum and maximum are in the correct positions), so return 0.
    • If i < j, the minimum is to the left of the maximum. The minimum needs to move i positions to the left, and the maximum needs to move n - 1 - j positions to the right. The total swaps is the sum of these.
    • If i > j, the minimum is to the right of the maximum. This case requires an additional swap because we need to account for the crossing of minimum and maximum elements during the process. The calculation is adjusted accordingly.

Time Complexity Analysis:

The algorithm involves a single pass through the array to find the indices i and j. Therefore, the time complexity is O(n), where n is the length of the input array.

Space Complexity Analysis:

The algorithm uses only a few variables to store indices and the length of the array. The space complexity is O(1), which is constant.

Code Implementation (Python):

class Solution:
    def minimumSwaps(self, nums: List[int]) -> int:
        i = j = 0
        for k, v in enumerate(nums):
            if v < nums[i] or (v == nums[i] and k < i):
                i = k
            if v >= nums[j] or (v == nums[j] and k > j):
                j = k
        return 0 if i == j else i + len(nums) - 1 - j - (i > j)

Code Implementation (Java):

class Solution {
    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        int i = 0, j = 0;
        for (int k = 0; k < n; ++k) {
            if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
                i = k;
            }
            if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
                j = k;
            }
        }
        if (i == j) {
            return 0;
        }
        return i + n - 1 - j - (i > j ? 1 : 0);
    }
}

Code Implementation (C++):

class Solution {
public:
    int minimumSwaps(vector<int>& nums) {
        int n = nums.size();
        int i = 0, j = 0;
        for (int k = 0; k < n; ++k) {
            if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
                i = k;
            }
            if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
                j = k;
            }
        }
        if (i == j) {
            return 0;
        }
        return i + n - 1 - j - (i > j);
    }
};

Code Implementation (Go):

func minimumSwaps(nums []int) int {
	var i, j int
	for k, v := range nums {
		if v < nums[i] || (v == nums[i] && k < i) {
			i = k
		}
		if v > nums[j] || (v == nums[j] && k > j) {
			j = k
		}
	}
	if i == j {
		return 0
	}
	if i < j {
		return i + len(nums) - 1 - j
	}
	return i + len(nums) - 2 - j
}

Code Implementation (TypeScript):

function minimumSwaps(nums: number[]): number {
    let i = 0;
    let j = 0;
    const n = nums.length;
    for (let k = 0; k < n; ++k) {
        if (nums[k] < nums[i] || (nums[k] == nums[i] && k < i)) {
            i = k;
        }
        if (nums[k] > nums[j] || (nums[k] == nums[j] && k > j)) {
            j = k;
        }
    }
    return i == j ? 0 : i + n - 1 - j - (i > j ? 1 : 0);
}

The provided code implements this algorithm efficiently and concisely in several programming languages. The core logic remains consistent across all versions.