We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Semi-Ordered Permutation

Number: 2785

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given a 0-indexed permutation of n integers, the goal is to rearrange the array so that the first element is 1 and the last element is n. The only allowed operation is swapping two adjacent elements. Return the minimum number of operations required to transform the array into a semi-ordered permutation.

Key Insights

  • Identify the current positions (indices) of 1 and n in the array.
  • To bring 1 to the beginning, it requires a number of swaps equal to its current index.
  • To bring n to the end, it requires a number of swaps equal to (n-1 - current index of n).
  • If the index of 1 is greater than the index of n, the swaps overlap resulting in one less swap overall.
  • The overall time complexity is O(n) since only a single pass is needed to find the indices, and constant additional work is performed.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution involves scanning through the given permutation to locate the positions of 1 and n. The number of swaps required to bring 1 to the beginning is equal to its current index (since each adjacent swap moves it one position to the left). Similarly, the number of swaps to bring n to the end is (n-1 - index of n). However, if the index of 1 comes after the index of n, one swap will effectively move both elements at the same time, so we subtract one from the total count. This approach uses simple arithmetic calculations and a single traversal to determine indices.

Code Solutions

# Function to calculate minimum swaps to reach semi-ordered permutation
def semi_ordered_permutation(nums):
    n = len(nums)
    # Find the index of element 1 and element n
    index_of_1 = nums.index(1)
    index_of_n = nums.index(n)
    
    # Calculate steps to move 1 to beginning and n to end
    swaps = index_of_1 + (n - 1 - index_of_n)
    
    # If 1 is to the right of n, one swap overlaps both moves
    if index_of_1 > index_of_n:
        swaps -= 1
    return swaps

# Example usage:
print(semi_ordered_permutation([2,1,4,3]))  # Expected output: 2
print(semi_ordered_permutation([2,4,1,3]))  # Expected output: 3
print(semi_ordered_permutation([1,3,4,2,5]))  # Expected output: 0
← Back to All Questions