2340. Minimum Adjacent Swaps to Make a Valid Array

MediumGreedyArray
Leetcode Link

Problem Description

You are provided with an array nums which is zero-indexed, meaning the indexing starts from 0. Your task is to sort the array in a specific way using only swaps between two adjacent elements. The goal is to have the smallest number positioned at the start (leftmost) of the array and the largest number at the end (rightmost) of the array. The array is considered valid when these conditions are met. Your objective is to determine the minimum number of such swaps required to make the array valid.

Intuition

To solve this problem, the strategy is to find the positions of the smallest and the largest elements in the array since only their positions matter for making the array valid. Typically, a linear scan through the array allows us to identify these elements and their indices.

Once the positions of the smallest and largest elements are known, there are a few cases to consider:

  • If the smallest element is already at the first (leftmost) position and the largest element is already at the last (rightmost) position, then no swaps are needed.
  • If the smallest and largest elements are not in their correct positions, they need to be swapped towards their respective ends. However, if the largest element is to the left of the smallest element, when the largest element is moved to the end, it effectively takes one swap less since the smallest element moves one place towards the beginning in the process.

The formula i + len(nums) - 1 - j - (i > j) reflects this logic, where i is the index of the smallest element, j is the index of the largest element, and len(nums) is the size of the array. The term (i > j) is a conditional that subtracts one from the total swap count if the largest element comes before the smallest element.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

In a binary min heap, the maximum element can be found in:

Solution Approach

The solution provided uses a single-pass algorithm to find the indices i and j, which represent the positions of the smallest and the largest elements in the nums array respectively. The algorithm iterates over each element in the array using a for loop and checks if the current element is less than or equal to the smallest element found so far, or if it is greater than or equal to the largest element found so far.

Here is the breakdown of how it works:

  1. Two variables i and j are initialized to 0, indicating that initially, we consider the first element as both the smallest and the largest.

  2. A for loop begins which examines each element indexed by k and compares its value v with the current smallest and the largest elements.

  3. For the smallest element (nums[i]), we have two conditions:

    • If v is less than nums[i], we update i to k because we have found a new smallest element.

    • If v is equal to nums[i] and k is less than i, we update i to k because we want the smallest element that is closest to the start of the array.

  4. Similarly, for the largest element (nums[j]), we have two conditions:

    • If v is greater than nums[j], we update j to k because we found a new largest element.

    • If v is equal to nums[j] and k is greater than j, we update j to k because we want the largest element that is closest to the end of the array.

  5. After the loop ends, we have the positions of the smallest and largest elements in i and j. The number of swaps required is then calculated with the following formula:

    1i + len(nums) - 1 - j - (i > j)

    The logic behind this formula is:

    • i + len(nums) - 1 - j calculates the total distance the smallest and largest elements need to move to reach their respective ends.

    • (i > j) serves as an adjustment in case the largest element is before the smallest element. If i is greater than j, we have moved the smallest element one step to the left already when moving the largest element to the end, thus requiring one less swap.

  6. The code finally returns 0 if i is equal to j, which implies that the smallest and largest element is the same, hence no swaps required. Otherwise, it returns the calculated number of swaps needed to organize the array properly.

This concise algorithm effectively solves the problem with a time complexity of O(n) since it requires only one pass through the array, and a space complexity of O(1) as it uses a constant amount of space.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Consider the array nums = [3, 1, 2, 4].

  1. Initialize i and j to 0. Initially, we consider the first element as the smallest and the largest one. So i = j = 0.

  2. Start the for loop with index k, iterating through the array from k = 1 to the end. The comparison process is as follows:

    • For k = 1: v = nums[1] = 1, which is less than nums[i] = 3. Thus, i is updated to 1.

    • For k = 2: v = nums[2] = 2. It doesn't change i because v is greater than nums[i] = 1, and it doesn't change j because v is less than nums[j] = 3.

    • For k = 3: v = nums[3] = 4, which is greater than nums[j] = 3. Thus, j is updated to 3.

  3. Now we have the positions of the smallest (1 for nums[i]) and largest elements (3 for nums[j]). We use the swap calculation formula:

    1i + len(nums) - 1 - j - (i > j)

    Here, len(nums) is 4, so plugging in the values, we get:

    11 + 4 - 1 - 3 - (1 > 3) => 1 + 4 - 1 - 3 - 0 => 1

    Therefore, the minimum number of swaps required is 1.

  4. The array after the swap process will look like this: [1, 3, 2, 4], where the smallest number 1 has been brought to the start and the largest 4 is at the end.

This walk-through demonstrates that a single scan of the array is sufficient to find the required number of swaps to sort the array according to the given conditions, and the calculation is straightforward once we have the positions of the smallest and largest elements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minimumSwaps(self, nums: List[int]) -> int:
5        # Initialize the positions of the minimum and maximum elements
6        min_position = max_position = 0
7      
8        # Iterate through the array to find the positions
9        for index, value in enumerate(nums):
10            # Update the position of the minimum element if a
11            # new minimum is found or if the same minimum is found at a lower index
12            if value < nums[min_position] or (value == nums[min_position] and index < min_position):
13                min_position = index
14          
15            # Update the position of the maximum element if a
16            # new maximum is found or if the same maximum is found at a higher index
17            if value > nums[max_position] or (value == nums[max_position] and index > max_position):
18                max_position = index
19      
20        # Calculate the number of swaps needed
21        swaps = 0 if min_position == max_position else min_position + (len(nums) - 1 - max_position)
22      
23        # If min_position is greater than max_position, one swap has been double counted
24        if min_position > max_position:
25            swaps -= 1
26      
27        return swaps
28
1class Solution {
2    // Function to find the minimum number of swaps required to make the given array sorted
3    public int minimumSwaps(int[] nums) {
4        int n = nums.length; // Length of the given array
5        int minIndex = 0, maxIndex = 0; // Initialize indices for minimum and maximum elements
6
7        // Loop through the array to find the indices for the minimum and maximum elements
8        for (int k = 0; k < n; ++k) {
9            // Update the index of the minimum element found so far
10            if (nums[k] < nums[minIndex] || (nums[k] == nums[minIndex] && k < minIndex)) {
11                minIndex = k;
12            }
13            // Update the index of the maximum element found so far
14            if (nums[k] > nums[maxIndex] || (nums[k] == nums[maxIndex] && k > maxIndex)) {
15                maxIndex = k;
16            }
17        }
18
19        // If the minimum and maximum elements are at the same position, no swaps are needed
20        if (minIndex == maxIndex) {
21            return 0;
22        }
23
24        // Calculate the number of swaps required
25        // The calculation is done by considering the positions of the minimum and maximum elements 
26        // and adjusting the swap count depending on their relative positions
27        int swaps = minIndex + n - 1 - maxIndex - (minIndex > maxIndex ? 1 : 0);
28      
29        // Return the number of swaps
30        return swaps;
31    }
32}
33
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    int minimumSwaps(vector<int>& nums) {
7        int numsSize = nums.size();         // Get the size of the input array
8        int minIndex = 0, maxIndex = 0;     // Initialize the indices for the minimum and maximum elements
9
10        // Loop through the array to find the minimum and maximum elements' indices
11        for (int k = 0; k < numsSize; ++k) {
12            // Update the index of the minimum element if a smaller element is found
13            // or if the same element is found at a smaller index
14            if (nums[k] < nums[minIndex] || (nums[k] == nums[minIndex] && k < minIndex)) {
15                minIndex = k;
16            }
17            // Update the index of the maximum element if a larger element is found
18            // or if the same element is found at a larger index
19            if (nums[k] > nums[maxIndex] || (nums[k] == nums[maxIndex] && k > maxIndex)) {
20                maxIndex = k;
21            }
22        }
23
24        // If the minimum and maximum elements are at the same index, no swaps are needed
25        if (minIndex == maxIndex) {
26            return 0;
27        }
28
29        // Calculate the number of swaps needed
30        // If minIndex is greater than maxIndex, one swap will be counted twice, so subtract one
31        int swaps = minIndex + numsSize - 1 - maxIndex - (minIndex > maxIndex);
32        return swaps;
33    }
34};
35
1/**
2 * Calculates the minimum number of swaps needed to bring the minimum and maximum elements
3 * to the ends of the array, with the minimum element at the start and the maximum at the end.
4 * @param {number[]} nums - Array of numbers for which to calculate the minimum number of swaps.
5 * @returns {number} - The minimum number of swaps required.
6 */
7function minimumSwaps(nums: number[]): number {
8    let minIndex = 0; // Index for the minimum element
9    let maxIndex = 0; // Index for the maximum element
10    const length = nums.length; // The length of the nums array
11
12    // Iterate over the array to find the indices of the minimum and maximum elements.
13    for (let k = 0; k < length; ++k) {
14        // Update minIndex if a smaller element is found or if the same element is found at a lower index
15        if (nums[k] < nums[minIndex] || (nums[k] === nums[minIndex] && k < minIndex)) {
16            minIndex = k;
17        }
18        // Update maxIndex if a larger element is found or if the same element is found at a higher index
19        if (nums[k] > nums[maxIndex] || (nums[k] === nums[maxIndex] && k > maxIndex)) {
20            maxIndex = k;
21        }
22    }
23
24    // Calculate the number of swaps required.
25    return minIndex === maxIndex 
26        ? 0 // If minIndex and maxIndex are the same, no swaps are needed.
27        : minIndex + (length - 1 - maxIndex) - (minIndex > maxIndex ? 1 : 0);
28    // The total swaps are normally the distance of minIndex from the start plus 
29    // distance of maxIndex from the end. If minIndex is after maxIndex, reduce one swap.
30}
31
Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

Time Complexity

The time complexity of the provided code is primarily determined by the single loop that iterates through the array nums. Since the loop runs for each element in the array, the time complexity is O(n), where n is the length of the array nums.

Space Complexity

The space complexity of the code is O(1) because it uses a fixed amount of extra space regardless of the size of the input array. The extra space is used for the variables i, j, k, and v, whose storage does not scale with the size of the input array.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫