algoadvance

A permutation of an array of integers is called semi-ordered if the first element is the smallest element in the array and the last element is the largest element in the array. Given a permutation nums of n integers, return the minimum number of swaps to make the permutation semi-ordered.

Example 1:

Input: nums = [2,1,4,3]
Output: 2
Explanation: In the first swap, we change the position of 2 and 1, nums = [1,2,4,3]. In the second swap, we change the position of 4 and 3, nums = [1,2,3,4].

Example 2:

Input: nums = [2,4,1,3]
Output: 3
Explanation: In the first swap, we change the position of 2 and 1, nums = [1,4,2,3]. In the second swap, we change the position of 4 and 2, nums = [1,2,4,3]. In the third swap, we change the position of 4 and 3, nums = [1,2,3,4].

Constraints:

• 2 <= nums.length <= 50
• 1 <= nums[i] <= 50
• nums is a permutation of the first n natural numbers.

Clarifying Questions

1. Can the array contain duplicate elements?
   • No, the array is a permutation of the first n natural numbers.
2. Is there always a unique solution for the given input?
   • Yes, since it is a permutation of the first n natural numbers, there is at least one way to reorder it to make it semi-ordered.

Strategy

To solve this problem, we’ll follow these steps:

1. Identify the indices of the smallest (min_val) and largest (max_val) elements.
2. Determine the number of swaps needed to bring min_val to the first position.
3. Determine the number of swaps needed to bring max_val to the last position.
4. Return the sum of these swaps unless the order of swaps affects each other (e.g., moving the minimum element past the maximum element might disrupt the count).

Code

def semiOrderedPermutation(nums):
    n = len(nums)
    
    min_val = min(nums)
    max_val = max(nums)
    
    min_idx = nums.index(min_val)
    max_idx = nums.index(max_val)
    
    # Swaps required to place the minimum at the start
    swaps_min = min_idx
    
    # Swaps required to place the maximum at the end
    swaps_max = n - 1 - max_idx
    
    # If min_idx is to the left of max_idx, the swaps do not interfere
    if min_idx < max_idx:
        return swaps_min + swaps_max
    else:
        # If min_idx is to the right of max_idx, they will interfere
        return swaps_min + swaps_max - 1

# Example 1
print(semiOrderedPermutation([2,1,4,3]))  # Output: 2

# Example 2
print(semiOrderedPermutation([2,4,1,3]))  # Output: 3

Time Complexity

• Finding min_val and max_val in the array takes O(n).
• Finding their indices also takes O(n).
• Therefore, the total time complexity of the solution is O(n).

Given the constraints (array length up to 50), this time complexity is optimal.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?