medium Minimum Adjacent Swaps to Make a Valid Array

Problem Statement

Given an integer array nums, return the minimum swaps required to make nums a valid array.

You can swap any two adjacent elements of the array.

An array is a valid array if it meets the following conditions:

• The largest element is at the rightmost position in the array.
• The smallest element is at the leftmost position in the array.
• If there are multiple smallest and largest elements, any of the smallest elements should be at the leftmost position and any of the largest should be at the rightmost position.

Examples

• Example 1:

  • Input: nums = [3, 1, 2]
  • Expected Output: 2
  • Justification: The first swap moves 3 to the second position by swapping with 1, and the second swap moves 3 to the third position by swapping with 2, positioning the smallest element (1) at the beginning and the largest element (3) at the end.

• Example 2:

  • Input: nums = [1, 2, 3, 4]
  • Expected Output: 0
  • Justification: This array already meets the criteria with the smallest element (1) at the start and the largest element (4) at the end, requiring no swaps.

• Example 3:

  • Input: nums = [3, 5, 4, 5, 1, 2]
  • Expected Output: 5
  • Justification: The smallest element (1) requires 4 swaps to move to the beginning, and after that the largest element (5) requires 1 swap to move to the rightmost position, considering the optimal path that minimizes overall swaps.

Solution

To solve this problem, we start by identifying the positions of the smallest and largest elements in the array. The strategy involves two main steps: moving the smallest element to the beginning and the largest to the end with adjacent swaps. This approach is efficient because it directly addresses the problem's requirements without unnecessary operations.

Initially, we focus on minimizing the swaps for the smallest element, considering its potential multiple occurrences and choosing the one closest to the start. Similarly, for the largest element, we aim to minimize its movement by selecting an occurrence closest to the end. This method is effective because it reduces the number of swaps by leveraging the initial positions of the target elements.

Step-by-Step Algorithm

1. Initialize two variables, minVal and maxVal, to store the minimum and maximum values found in the array. Set minVal to the highest possible integer value and maxVal to the lowest possible integer value to ensure they are updated during the first comparison.

2. Initialize two variables, minIndex and maxIndex, to store the positions of the minimum and maximum values within the array.

3. Iterate through the array once, from the first to the last element:

   • For each element, if it is less than minVal, update minVal with this element's value and minIndex with the current index.
   • For each element, if it is greater than or equal to maxVal, update maxVal with this element's value and maxIndex with the current index.

4. Calculate the total number of swaps needed to move the smallest element to the beginning and the largest element to the end. This is done by adding minIndex (the number of swaps needed to move the smallest element to the start) to (n - 1 - maxIndex) (the number of swaps needed to move the largest element to the end), where n is the length of the array.

5. If the smallest element is positioned after the largest element (minIndex > maxIndex), subtract one swap from the total. This adjustment is necessary because moving the largest element towards the end will simultaneously move the smallest element towards the start, thus overlapping one swap.

6. Return the calculated total number of swaps.

Algorithm Walkthrough

1. Initialization:

   • minVal is set to Integer.MAX_VALUE.
   • maxVal is set to Integer.MIN_VALUE.
   • minIndex and maxIndex are both initialized but not yet set.

2. Iterate through the array:

   • Index 0: Encounter 3. Update minVal to 3 and Update maxVal to 3 and maxIndex to 0.
   • Index 1: Encounter 5. minVal remains unchanged. Update maxVal to 5 and maxIndex to 1.
   • Index 2: Encounter 4. No updates to minVal or maxVal.
   • Index 3: Encounter another 5. minVal remains unchanged. Update maxVal to 5 (same value, higher index) and maxIndex to 3.
   • Index 4: Encounter 1. Update minVal to 1 and minIndex to 4. maxVal remains unchanged.
   • Index 5: Encounter 2. No updates to minVal or maxVal.

3. Calculate total swaps:

   • minIndex is 4, and maxIndex is 3.
   • Total swaps = minIndex + (n - 1 - maxIndex) = 4 + (6 - 1 - 3) = 4 + 2 = 6.

4. Adjust for overlap:

   • Since minIndex > maxIndex, we understand that one swap has been double-counted.
   • Adjust the total swaps by subtracting one: 6 - 1 = 5.

5. Conclusion:

   • The minimum number of swaps required to make the array valid is 5.

Code

public class Solution {

  // Function to find the minimum number of swaps required
  // to sort the given array in non-decreasing order
  public int minSwaps(int[] nums) {
    // Get the length of the input array
    int n = nums.length;

    // Initialize variables to store minimum and maximum values
    int minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;

    // Initialize variables to store indices of minimum and maximum values
    int minIndex = -1, maxIndex = -1;

    // Iterate through the array to find minimum and maximum values
    for (int i = 0; i < n; i++) {
      // Update minimum value and its index if found
      if (nums[i] < minVal) {
        minVal = nums[i];
        minIndex = i;
      }
      // Update maximum value and its index if found
      if (nums[i] >= maxVal) {
        maxVal = nums[i];
        maxIndex = i;
      }
    }

    // Calculate the number of swaps required
    int swaps = minIndex + (n - 1 - maxIndex);

    // Adjust swaps if minimum index is to the right of maximum index
    if (minIndex > maxIndex) swaps--;

    // Return the minimum number of swaps required
    return swaps;
  }

  // Main method to test the minSwaps function
  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test cases
    System.out.println(solution.minSwaps(new int[] { 3, 1, 2 })); // Example 1
    System.out.println(solution.minSwaps(new int[] { 1, 2, 3, 4 })); // Example 2
    System.out.println(solution.minSwaps(new int[] { 3, 5, 4, 5, 1, 2 })); // Example 3
  }
}

Complexity Analysis

Time Complexity:

The time complexity of the minSwaps method is , where n is the number of elements in the array nums. This efficiency is due to a single pass through the array to find the positions of the minimum and maximum elements, which requires looking at each element exactly once.

Space Complexity:

The space complexity is because the method uses a constant amount of extra space regardless of the input array size.