Posts Minimum Adjacent Swaps to Make a Valid Array
Post
Cancel

Minimum Adjacent Swaps to Make a Valid Array

Problem Description

You are given a 0-indexed integer array nums.

Swaps of adjacent elements are able to be performed on nums.

A valid array meets the following conditions:

  • The largest element (any of the largest elements if- there are multiple) is at the rightmost position in the- array.
  • The smallest element (any of the smallest elements if there are multiple) is at the leftmost position in the array.

Return the minimum swaps required to make nums a valid array.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {

    public int minimumSwaps(int[] nums) {

        int n = nums.length;

        int minIndex = 0;
        int maxIndex = 0;

        // find left most smallest element
        // find right most largest element
        for(int i = 0; i < n; i++){

            // Update minIndex if a smaller element is found
            if(nums[i] < nums[minIndex]){
                minIndex = i;
            }

            // we need to find right most largest element
            // that is why we take equal here also
            if(nums[i] >= nums[maxIndex]){
                maxIndex = i;
            }

        }

        // If the largest element's index is before the smallest element's index
        // Subtract 1 to account for the overlap of swaps
        // If we keep moving, let's say, smallest element towards left, the largest element will automatically move towards right by 1 step
        // So, we need to handle this case
        if(maxIndex < minIndex){
            return minIndex + (n - maxIndex - 1) - 1;
        }

        // Otherwise, simply push smallest to left and largest to right
        return minIndex + (n - maxIndex - 1);
    }
}
This post is licensed under CC BY 4.0 by the author.