Minimum Adjacent Swaps to Make a Valid Array
- 2 min read
- Array
- LC-Medium
3 years ago
Solution
- Just find the index of the maximum and minimum numbers, and calculate the answer based on the difference in indexes
- The only difference is that when the
min_idx > max_idx(when the smaller number exists after the bigger number), moving the min_num to the leftmost will move the max_num to the right by 1, hence, number of swaps will decrease by 1, i.e. one of the swaps counts towards one move for the other, so you decrease the answer by 1- For example,
[2, 1]only needs one swap operation, not two, even though the minimum and maximum numbers are both not in the correct positions
- For example,
- To understand
(n - max_idx - 1) + min_idx, just do a dry run to figure out the math
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def minimumSwaps(self, nums: List[int]) -> int:
n = len(nums)
min_ele = min(nums)
max_ele = max(nums)
for max_idx in range(n - 1, -1, -1):
if nums[max_idx] == max_ele:
break
for min_idx in range(n):
if nums[min_idx] == min_ele:
break
ans = (n - max_idx - 1) + min_idx
if min_idx > max_idx:
ans -= 1
return ans