Problem Description

You have an integer array nums indexed from 0. You can swap adjacent elements in this array.

Your goal is to make the array "valid" by meeting two conditions:

• The smallest element must be at the leftmost position (index 0)
• The largest element must be at the rightmost position (last index)

If there are multiple elements with the same minimum or maximum value:

• Any of the minimum values can be at the leftmost position
• Any of the maximum values can be at the rightmost position

You need to find the minimum number of adjacent swaps required to achieve this valid configuration.

For example, if nums = [3, 4, 5, 5, 3, 1]:

• The minimum value is 1 (at index 5)
• The maximum value is 5 (appears at indices 2 and 3)
• You would need to move 1 to the leftmost position
• You would need to move one of the 5s to the rightmost position (the one at index 3 is already closer to the right)

The solution tracks:

• Index i: position of the first occurrence of the minimum value
• Index j: position of the last occurrence of the maximum value

The number of swaps depends on the relative positions:

• If i == j: the same element is both min and max (all elements are equal), so 0 swaps needed
• If i < j: min is left of max, need i + (n-1-j) swaps
• If i > j: min is right of max, need i + (n-1-j) - 1 swaps (subtract 1 because moving min left will also move max one position right)

Intuition

The key insight is that we only need to move two specific elements: the minimum value to the leftmost position and the maximum value to the rightmost position. Since we can only swap adjacent elements, we need to count how many positions each element needs to move.

Let's think about this step by step:

1. Finding the right elements to move: We need to identify which minimum and maximum elements to move. If there are multiple minimums, we want the leftmost one (already closest to position 0). If there are multiple maximums, we want the rightmost one (already closest to the last position). This minimizes the number of swaps needed.

2. Counting swaps for each element:

   • To move the minimum from position i to position 0, we need exactly i swaps (moving it left by swapping with each element to its left)
   • To move the maximum from position j to position n-1, we need exactly n-1-j swaps (moving it right by swapping with each element to its right)

3. The overlap consideration: Here's the clever part - if the minimum element is initially to the right of the maximum element (i > j), something interesting happens. As we move the minimum leftward, it will eventually pass by the maximum element. This passing swap contributes to both movements! It moves the minimum one step left AND the maximum one step right. So we've counted this swap twice - once in the minimum's movement and once in the maximum's movement. That's why we subtract 1 in this case.

4. Special case: If i == j, the same element is both the minimum and maximum (all array elements are equal), so the array is already valid with 0 swaps.

The formula i + (n-1-j) - (i > j) elegantly captures all these cases:

• Basic swaps needed: i for minimum + (n-1-j) for maximum
• Subtract 1 if i > j to account for the double-counted swap
• The expression (i > j) evaluates to 1 if true, 0 if false, perfectly handling both cases

Learn more about Greedy patterns.

Solution Approach

The implementation uses a single-pass traversal with index tracking to efficiently find the required positions:

1. Initialize index trackers:

i = j = 0

• i tracks the index of the leftmost minimum value
• j tracks the index of the rightmost maximum value

2. Traverse the array once to find optimal positions:

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

For the minimum value tracking:

• Update i if we find a smaller value: v < nums[i]
• Also update i if we find an equal minimum that's more to the left: v == nums[i] and k < i
• This ensures we get the leftmost occurrence of the minimum value

For the maximum value tracking:

• Update j if we find a larger value: v > nums[j]
• Also update j if we find an equal maximum: v >= nums[j]
• The >= operator naturally gives us the rightmost occurrence since we're traversing left to right

3. Calculate the minimum swaps:

return 0 if i == j else i + len(nums) - 1 - j - (i > j)

This handles three cases:

• Case 1: i == j - The same element is both min and max (all elements equal), return 0
• Case 2: i < j - Min is left of max, return i + (n-1-j) swaps
• Case 3: i > j - Min is right of max, return i + (n-1-j) - 1 swaps

The expression (i > j) evaluates to True (1) or False (0), automatically subtracting 1 when the minimum needs to pass the maximum during swapping.

Time Complexity: O(n) - Single pass through the array
Space Complexity: O(1) - Only using two index variables

Example Walkthrough

Let's walk through the solution with nums = [2, 1, 4, 1, 3]:

Step 1: Find the positions of elements to move

We traverse the array to find:

• The leftmost occurrence of the minimum value
• The rightmost occurrence of the maximum value

*At index 3, we find another 1, but we don't update i because we want the leftmost minimum (i=1 is already left of k=3)

Final positions: i = 1 (minimum value 1), j = 2 (maximum value 4)

Step 2: Calculate swaps needed

Since i < j (1 < 2), we use the formula: i + (n-1-j)

• Swaps to move min from index 1 to index 0: i = 1 swap
• Swaps to move max from index 2 to index 4: (5-1-2) = 2 swaps
• Total: 1 + 2 = 3 swaps

Step 3: Verify with actual swaps

Starting array: [2, 1, 4, 1, 3]

Move minimum (1 at index 1) to the left:

• Swap indices 0 and 1: [1, 2, 4, 1, 3] (1 swap)

Move maximum (4 at index 2) to the right:

• Swap indices 2 and 3: [1, 2, 1, 4, 3] (1 swap)
• Swap indices 3 and 4: [1, 2, 1, 3, 4] (1 swap)

Final array: [1, 2, 1, 3, 4] ✓ Total swaps: 3 ✓

Alternative example to show the overlap case:

For nums = [3, 4, 1, 5]:

• i = 2 (minimum value 1 at index 2)
• j = 3 (maximum value 5 at index 3)
• Since i < j, swaps = 2 + (4-1-3) - 0 = 2 + 0 = 2

But if we had nums = [3, 5, 1, 4]:

• i = 2 (minimum value 1 at index 2)
• j = 1 (maximum value 5 at index 1)
• Since i > j, swaps = 2 + (4-1-1) - 1 = 2 + 2 - 1 = 3

The subtraction of 1 accounts for when the minimum (moving left) passes the maximum (moving right) - this single swap helps both elements reach their destinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums.

The algorithm performs a single pass through the array using one for loop with enumerate(nums). During each iteration, it performs constant-time operations:

• Comparing values to find the minimum element (with leftmost position preference)
• Comparing values to find the maximum element (with rightmost position preference)
• Updating indices i and j when necessary

Since we iterate through all n elements exactly once and perform O(1) operations for each element, the total time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

• Two integer variables i and j to store indices
• Loop variable k and value v from enumeration
• These variables don't scale with input size

The space usage remains constant regardless of the input array size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Finding the Rightmost Maximum Index

Pitfall: Using v > nums[j] instead of v >= nums[j] when updating the maximum index.

# WRONG - This finds the leftmost maximum, not rightmost
for k, v in enumerate(nums):
    if v > nums[j]:  # Missing the equals case
        j = k

Why it's wrong: When there are multiple maximum values, this will only update j when finding a strictly greater value, resulting in the leftmost occurrence of the maximum rather than the rightmost.

Solution: Always use >= to ensure the index updates for equal maximum values during left-to-right traversal:

# CORRECT - Finds rightmost maximum
for k, v in enumerate(nums):
    if v >= nums[j]:  # Includes equal values
        j = k

2. Forgetting to Handle the Overlap Case

Pitfall: Not subtracting 1 when the minimum element is to the right of the maximum element.

# WRONG - Always adds both distances
return i + len(nums) - 1 - j

Why it's wrong: When i > j, moving the minimum element leftward will push the maximum element one position to the right, effectively reducing the total swaps needed by 1.

Solution: Check if indices overlap and adjust accordingly:

# CORRECT - Accounts for overlap
return i + len(nums) - 1 - j - (i > j)

3. Finding the Rightmost Minimum Instead of Leftmost

Pitfall: Not properly handling duplicate minimum values, resulting in finding a suboptimal starting position.

# WRONG - May not find the leftmost minimum
for k, v in enumerate(nums):
    if v <= nums[i]:  # This would find rightmost minimum
        i = k

Why it's wrong: Using <= for minimum tracking would continuously update i for equal values, giving us the rightmost occurrence when we need the leftmost.

Solution: Only update for strictly smaller values, or for equal values that appear earlier:

# CORRECT - Finds leftmost minimum
for k, v in enumerate(nums):
    if v < nums[i]:  # Strictly less than
        i = k

4. Initializing Indices Incorrectly

Pitfall: Initializing indices to invalid values or not considering the first element.

# WRONG - May cause index out of bounds or miss first element
min_index = -1
max_index = len(nums)

Solution: Initialize both indices to 0, treating the first element as the initial min and max:

# CORRECT - Start with first element as reference
min_index = 0
max_index = 0