2340. Minimum Adjacent Swaps to Make a Valid Array
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.
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:
-
Two variables
i
andj
are initialized to 0, indicating that initially, we consider the first element as both the smallest and the largest. -
A
for
loop begins which examines each element indexed byk
and compares its valuev
with the current smallest and the largest elements. -
For the smallest element (
nums[i]
), we have two conditions:-
If
v
is less thannums[i]
, we updatei
tok
because we have found a new smallest element. -
If
v
is equal tonums[i]
andk
is less thani
, we updatei
tok
because we want the smallest element that is closest to the start of the array.
-
-
Similarly, for the largest element (
nums[j]
), we have two conditions:-
If
v
is greater thannums[j]
, we updatej
tok
because we found a new largest element. -
If
v
is equal tonums[j]
andk
is greater thanj
, we updatej
tok
because we want the largest element that is closest to the end of the array.
-
-
After the loop ends, we have the positions of the smallest and largest elements in
i
andj
. 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. Ifi
is greater thanj
, 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.
-
-
The code finally returns
0
ifi
is equal toj
, 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach. Consider the array nums = [3, 1, 2, 4]
.
-
Initialize
i
andj
to0
. Initially, we consider the first element as the smallest and the largest one. Soi = j = 0
. -
Start the
for
loop with indexk
, iterating through the array fromk = 1
to the end. The comparison process is as follows:-
For
k = 1
:v = nums[1] = 1
, which is less thannums[i] = 3
. Thus,i
is updated to1
. -
For
k = 2
:v = nums[2] = 2
. It doesn't changei
becausev
is greater thannums[i] = 1
, and it doesn't changej
becausev
is less thannums[j] = 3
. -
For
k = 3
:v = nums[3] = 4
, which is greater thannums[j] = 3
. Thus,j
is updated to3
.
-
-
Now we have the positions of the smallest (
1
fornums[i]
) and largest elements (3
fornums[j]
). We use the swap calculation formula:1i + len(nums) - 1 - j - (i > j)
Here,
len(nums)
is4
, 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
. -
The array after the swap process will look like this:
[1, 3, 2, 4]
, where the smallest number1
has been brought to the start and the largest4
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
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.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Greedy Introduction div class responsive iframe iframe 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 div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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