We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Adjacent Swaps to Make a Valid Array

Number: 2474

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given an integer array, you can swap only adjacent elements. The array is considered valid if the smallest element (any one if there are multiple) is at index 0 and the largest element (any one if there are multiples) is at the last index. The goal is to determine the minimum number of adjacent swaps required to rearrange the array into a valid state.

Key Insights

  • Identify the leftmost occurrence of the smallest element and the rightmost occurrence of the largest element.
  • The smallest element requires a number of swaps equal to its index (to move it to index 0).
  • The largest element requires (n - 1 - its index) swaps (to move it to the last position).
  • If the smallest element is originally placed to the right of the largest element, one swap will affect both, so reduce the total count by one.

Space and Time Complexity

Time Complexity: O(n) – scanning the array a couple of times. Space Complexity: O(1) – using constant extra space.

Solution

First, scan the array to determine:

  1. The leftmost index where the minimum value appears.
  2. The rightmost index where the maximum value appears. Then, calculate the minimum swaps as:   swaps = (minIndex) + ((n - 1) - maxIndex) If minIndex > maxIndex (i.e., the smallest element is to the right of the maximum element), subtract one from the total swaps due to the overlapping swap effect. This approach directly maps to the operations allowed (adjacent swaps) and guarantees the minimal number of moves.

Code Solutions

# Function to compute minimum adjacent swaps required
def min_swaps(nums):
    n = len(nums)
    # Find the minimum value in the array and the leftmost index where it appears.
    min_val = min(nums)
    min_index = nums.index(min_val)

    # Find the maximum value in the array and the rightmost index where it appears.
    max_val = max(nums)
    max_index = -1
    for i in range(n - 1, -1, -1):
        if nums[i] == max_val:
            max_index = i
            break

    # Calculate the swaps needed: moves for minimum + moves for maximum.
    swaps = min_index + ((n - 1) - max_index)
    # Adjust if the minimum element is to the right of the maximum element.
    if min_index > max_index:
        swaps -= 1
    return swaps

# Example usage:
if __name__ == "__main__":
    # Test case 1: Expected output is 6.
    nums = [3, 4, 5, 5, 3, 1]
    print(min_swaps(nums))  # Output: 6

    # Test case 2: Expected output is 0 (array is already valid).
    nums = [9]
    print(min_swaps(nums))  # Output: 0
← Back to All Questions