Minimum Adjacent Swaps to Make a Valid Array

Medium

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed integer array nums. A valid array is defined as an array nums where for each index i such that 1 <= i < nums.length, nums[i - 1] <= nums[i].

You can perform the following operation on the array any number of times:

Choose an index i such that 0 <= i < nums.length - 1 and swap the elements nums[i] and nums[i + 1].

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

Example 1:

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
First, swap 1 and 5. nums becomes [3,4,1,5,2]
Second, swap 1 and 4. nums becomes [3,1,4,5,2]
The array [3,1,4,5,2] is now a valid array since the element at each index is greater than or equal to the element at the preceding index.
It can be shown that 2 is the minimum number of swaps required to make nums a valid array.

Example 2:

Input: nums = [9,8,4,3,5]
Output: 6
Explanation: 
First, swap 3 and 4. nums becomes [9,8,3,4,5]
Second, swap 3 and 8. nums becomes [9,3,8,4,5]
Third, swap 3 and 9. nums becomes [3,9,8,4,5]
Fourth, swap 4 and 8. nums becomes [3,9,4,8,5]
Fifth, swap 4 and 9. nums becomes [3,4,9,8,5]
Sixth, swap 5 and 8. nums becomes [3,4,9,5,8]
The array [3,4,9,5,8] is now a valid array since the element at each index is greater than or equal to the element at the preceding index.
It can be shown that 6 is the minimum number of swaps required to make nums a valid array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Try coding it in LeetCode

Minimum Adjacent Swaps to Make a Valid Array

Medium

Asked by:

6 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed integer array nums. A valid array is defined as an array nums where for each index i such that 1 <= i < nums.length, nums[i - 1] <= nums[i].

You can perform the following operation on the array any number of times:

Choose an index i such that 0 <= i < nums.length - 1 and swap the elements nums[i] and nums[i + 1].

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

Example 1:

Input: nums = [3,4,5,1,2]
Output: 2
Explanation: 
First, swap 1 and 5. nums becomes [3,4,1,5,2]
Second, swap 1 and 4. nums becomes [3,1,4,5,2]
The array [3,1,4,5,2] is now a valid array since the element at each index is greater than or equal to the element at the preceding index.
It can be shown that 2 is the minimum number of swaps required to make nums a valid array.

Example 2:

Input: nums = [9,8,4,3,5]
Output: 6
Explanation: 
First, swap 3 and 4. nums becomes [9,8,3,4,5]
Second, swap 3 and 8. nums becomes [9,3,8,4,5]
Third, swap 3 and 9. nums becomes [3,9,8,4,5]
Fourth, swap 4 and 8. nums becomes [3,9,4,8,5]
Fifth, swap 4 and 9. nums becomes [3,4,9,8,5]
Sixth, swap 5 and 8. nums becomes [3,4,9,5,8]
The array [3,4,9,5,8] is now a valid array since the element at each index is greater than or equal to the element at the preceding index.
It can be shown that 6 is the minimum number of swaps required to make nums a valid array.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array?
Can the input array be empty or null?
Are there any duplicate numbers in the array, and if so, how should they be handled in determining the minimum swaps?
If the array is already valid, should I return 0?
By "valid", do you mean the smallest element is at the beginning of the array and the largest element is at the end?

Brute Force Solution

Approach

The brute force approach to finding the fewest swaps involves checking every single possible arrangement of the numbers. We explore each arrangement, count how many swaps it would take to achieve that order, and ultimately keep track of the smallest number of swaps we find across all arrangements. Think of it like trying to sort a deck of cards by literally shuffling them in every possible order until you find the best one.

Here's how the algorithm would work step-by-step:

First, consider all the different orders you could put the numbers in. Imagine writing down every possible sequence.
For each of these sequences, figure out how many swaps it would take to rearrange the original list into that specific sequence.
Keep a running record of the smallest number of swaps you've seen so far. Start with a very large number.
Every time you calculate the number of swaps for a new sequence, compare it to the smallest number you've recorded.
If the new sequence takes fewer swaps than the current minimum, update your record.
Once you've gone through absolutely every possible sequence, the number you have recorded is the answer: the minimum number of swaps needed.

Code Implementation

import itertools

def minimum_adjacent_swaps_brute_force(numbers):
    minimum_swaps = float('inf')

    # Iterate through all permutations of the numbers
    for permutation in itertools.permutations(numbers):
        swap_count = 0
        current_arrangement = list(numbers)

        # Calculate swaps to achieve the permutation
        for i in range(len(numbers)):
            if current_arrangement[i] != permutation[i]:

                # Find the correct element's index
                correct_element_index = current_arrangement.index(permutation[i])

                # Perform swaps to bring it to the correct position
                for j in range(correct_element_index, i, -1):
                    current_arrangement[j], current_arrangement[j - 1] = \
                        current_arrangement[j - 1], current_arrangement[j]
                    swap_count += 1

        # Update minimum swaps
        minimum_swaps = min(minimum_swaps, swap_count)

    return minimum_swaps

def is_valid_array(arr):
    if not arr:
        return True
    maximum_element = max(arr)
    minimum_element = min(arr)
    max_index = arr.index(maximum_element)
    min_index = arr.index(minimum_element)
    if max_index < min_index:
        for i in range(max_index):
            if arr[i] < arr[i+1]:
                return False
        for i in range(max_index, min_index):
            if arr[i] > arr[i+1]:
                return False
        for i in range(min_index, len(arr)-1):
            if arr[i] < arr[i+1]:
                return False
    else:
        for i in range(min_index):
            if arr[i] < arr[i+1]:
                return False
        for i in range(min_index, max_index):
            if arr[i] < arr[i+1]:
                return False
        for i in range(max_index, len(arr)-1):
            if arr[i] > arr[i+1]:
                return False
    return True

def minimum_adjacent_swaps_to_make_valid_array(numbers):
    minimum_swaps_needed = float('inf')

    # Iterate through all possible permutations.
    for permutation in itertools.permutations(numbers):
        permutation_list = list(permutation)

        # Only consider valid arrays for optimization
        if is_valid_array(permutation_list):
            swaps_needed = 0
            temporary_array = list(numbers)

            # Calculate number of swaps to form permutation.
            for i in range(len(numbers)):
                if temporary_array[i] != permutation_list[i]:
                    correct_element_index = temporary_array.index(permutation_list[i])

                    # Move the correct element to the current position.
                    for j in range(correct_element_index, i, -1):
                        temporary_array[j], temporary_array[j - 1] = \
                            temporary_array[j - 1], temporary_array[j]
                        swaps_needed += 1

            # Update minimum swaps required.
            minimum_swaps_needed = min(minimum_swaps_needed, swaps_needed)

    return minimum_swaps_needed

Big(O) Analysis

Time Complexity

O(n! * n) – The algorithm considers all permutations of the input array of size n, which results in n! possible arrangements. For each permutation, it calculates the number of swaps needed to transform the original array into that permutation. Calculating the number of swaps for a single permutation requires at most n operations to compare the original array to the permuted array. Therefore, the total time complexity is proportional to n! multiplied by n, representing the cost of iterating over permutations and then comparing that permutation to the initial state.

Space Complexity

O(N!) – The described brute force approach explores all possible arrangements of the input array. To generate these permutations, it implicitly uses a recursion stack. In the worst case, the recursion depth goes as deep as N, where N is the number of elements in the input array. However, storing all N! permutations, or generating them iteratively one by one, would still imply a storage need proportional to the number of permutations. Therefore the auxiliary space used is O(N!).

Optimal Solution

Approach

To efficiently arrange the array, we focus on placing the smallest and largest numbers in their required positions with the fewest moves. Instead of exhaustively checking all possible arrangements, we strategically minimize the number of swaps required to achieve the target configuration.

Here's how the algorithm would work step-by-step:

First, find the smallest number and the largest number in the array.
Determine the best spot for the smallest number (the beginning) and the largest number (the end).
Count how many steps it will take to move the smallest number to its desired location.
Count how many steps it will take to move the largest number to its desired location. Be careful, because moving the smallest number might have changed the largest number's position!
Add the number of steps for the smallest and largest numbers together. This gives the fewest number of swaps needed.

Code Implementation

def minimum_swaps(array_numbers):
    smallest_number = min(array_numbers)
    largest_number = max(array_numbers)

    smallest_index = array_numbers.index(smallest_number)
    largest_index = array_numbers.index(largest_number)

    # Calculate the number of swaps to move
    # the smallest number to the beginning.
    swaps_for_smallest = smallest_index

    # Account for the case where the largest
    # number is before the smallest number.
    if largest_index < smallest_index:
        swaps_for_largest = len(array_numbers) - 1 - largest_index

    else:
        swaps_for_largest = len(array_numbers) - 1 - largest_index

    # Moving smallest might shift the largest, correct the swaps.
    if smallest_index < largest_index:
        total_swaps = swaps_for_smallest + swaps_for_largest

    else:
        total_swaps = swaps_for_smallest + swaps_for_largest

    return total_swaps

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the array once to find the smallest and largest numbers, which takes O(n) time. Subsequently, it determines the number of swaps required to move these elements to their desired positions. This involves a few constant-time operations (index calculations and potentially a single adjustment to the largest number's index), which do not depend on the size of the input array. Therefore, the dominant factor in the time complexity is the initial search for the minimum and maximum values, resulting in a total time complexity of O(n).

Space Complexity

O(1) – The algorithm primarily uses a few integer variables to store the indices of the smallest and largest elements, and to count the swaps. The number of these variables remains constant regardless of the input array's size, N. Therefore, the auxiliary space used by the algorithm does not scale with the input size. Consequently, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately as no swaps are needed for an empty array.
Array with a single element	Return 0 immediately as a single element array is always valid.
Array with all identical elements	The algorithm should correctly identify the first occurrence of the maximum and minimum elements, resulting in minimal swaps even with duplicates.
Array where the minimum or maximum element is at the beginning or end	The algorithm should correctly account for elements already in their desired positions and avoid unnecessary swaps.
Array with large number of elements (scalability)	Ensure that the algorithm's time complexity is optimized to avoid time limit exceeded errors, potentially using linear time solutions for finding min/max.
Array with duplicate minimum or maximum values	The algorithm should pick the first occurrence of the minimum and maximum values to minimize swaps.
Integer overflow if array size is very large	Use appropriate data types (e.g., long) to prevent potential integer overflow when calculating swap counts, especially if the array size is near the maximum integer value.
Array already sorted in ascending or descending order	The algorithm should correctly handle this case, requiring swaps to move max to the front and min to the end.