Problem Description

You have an array nums that is a permutation of integers from 1 to n. A permutation means it contains each number from 1 to n exactly once, but in some order.

The goal is to make this permutation "semi-ordered," which means:

• The first element must be 1
• The last element must be n

To achieve this, you can perform swaps, but with a restriction: you can only swap two adjacent elements at a time.

For example, if you have [3, 1, 2, 4], you could swap positions 0 and 1 to get [1, 3, 2, 4], then swap positions 2 and 3 to get [1, 3, 4, 2], and finally swap positions 1 and 2 to get [1, 4, 3, 2].

The task is to find the minimum number of such adjacent swaps needed to make the array semi-ordered.

The solution works by finding where 1 and n are currently located in the array. If 1 is at index i, it needs i swaps to move it to the front (position 0). If n is at index j, it needs n - 1 - j swaps to move it to the end (position n-1).

However, there's a special case to consider: if 1 is to the right of n initially (i.e., i > j), then as we move 1 leftward and n rightward, they will pass each other once, which means we've counted one swap twice. In this case, we need to subtract 1 from the total count.

The formula becomes:

• If i < j: total swaps = i + (n - 1 - j) = i + n - j - 1
• If i > j: total swaps = i + (n - 1 - j) - 1 = i + n - j - 2

Intuition

The key insight is that we only need to focus on two specific elements: 1 and n. All other elements don't matter for making the permutation semi-ordered.

Since we can only swap adjacent elements, moving an element from position i to position j requires exactly |i - j| swaps. Think of it like bubble sort - to move an element left by one position, we swap it with its left neighbor; to move it right by one position, we swap it with its right neighbor.

Let's think about what needs to happen:

• Element 1 needs to reach position 0 (the front)
• Element n needs to reach position n-1 (the end)

If 1 starts at position i, it needs exactly i leftward moves (swaps) to reach the front. If n starts at position j, it needs exactly n - 1 - j rightward moves to reach the end.

Initially, we might think the answer is simply i + (n - 1 - j). However, there's a subtle detail: what if 1 and n need to cross paths?

Consider when 1 is initially to the right of n (position i > j). As we move 1 leftward and n rightward, at some point they'll be adjacent and need to swap positions. This swap contributes to both elements' movement - it moves 1 one step left AND moves n one step right simultaneously. We've counted this swap twice in our formula, so we need to subtract 1.

When 1 is initially to the left of n (position i < j), they never meet during their journeys to their destinations, so no adjustment is needed.

This leads us to the elegant formula where we add i + n - j - k, where k = 1 when they don't cross paths and k = 2 when they do.

Solution Approach

The implementation is straightforward once we understand the problem:

1. Find the positions of key elements: Use the index() method to locate where 1 and n are in the array. Store these positions as i and j respectively.

2. Determine if elements will cross: Check if i < j (meaning 1 is to the left of n).

   • If i < j: The elements won't cross during their movements, so we set k = 1
   • If i > j: The elements will cross paths, counting one swap twice, so we set k = 2

3. Calculate the minimum swaps: Apply the formula i + n - j - k

   • i: number of swaps to move 1 to position 0
   • n - j - 1: number of swaps to move n to position n-1
   • Simplifying: i + (n - j - 1) = i + n - j - 1
   • Adjust by subtracting an additional 1 if elements cross: i + n - j - 2

The solution uses a ternary operator to elegantly handle both cases: k = 1 if i < j else 2, then returns i + n - j - k.

Time Complexity: O(n) for finding the indices of 1 and n using the index() method.

Space Complexity: O(1) as we only use a constant amount of extra space for variables i, j, and k.

The beauty of this solution lies in its simplicity - rather than simulating the actual swaps, we mathematically determine the exact number of moves needed based on the initial positions of just two elements.

Example Walkthrough

Let's walk through the solution with a concrete example: nums = [2, 4, 1, 3]

Step 1: Identify key positions

• Find where 1 is located: i = 2 (at index 2)
• Find where n = 4 is located: j = 1 (at index 1)

Step 2: Visualize what needs to happen

• Current state: [2, 4, 1, 3]
• Target state: [1, ?, ?, 4] (we need 1 at the front and 4 at the end)

Step 3: Count the moves for each element

• To move 1 from index 2 to index 0: needs 2 leftward swaps
  • [2, 4, 1, 3] → [2, 1, 4, 3] (swap positions 1 and 2)
  • [2, 1, 4, 3] → [1, 2, 4, 3] (swap positions 0 and 1)
• To move 4 from index 1 to index 3: needs 2 rightward swaps
  • Starting from [1, 2, 4, 3]:
  • [1, 2, 4, 3] → [1, 2, 3, 4] (swap positions 2 and 3)

Step 4: Check if elements cross paths

• Since i = 2 > j = 1, element 1 is initially to the right of element 4
• This means they will cross paths during their movements
• When they cross, one swap moves both elements simultaneously
• We've counted this swap in both elements' move counts, so we need to subtract 1

Step 5: Calculate using the formula

• Since i > j, we use k = 2
• Total swaps = i + n - j - k = 2 + 4 - 1 - 2 = 3

Verification by simulating the swaps:

1. [2, 4, 1, 3] → [2, 1, 4, 3] (swap indices 1 and 2, moving 1 left)
2. [2, 1, 4, 3] → [1, 2, 4, 3] (swap indices 0 and 1, moving 1 left)
3. [1, 2, 4, 3] → [1, 2, 3, 4] (swap indices 2 and 3, moving 4 right)

Indeed, we need exactly 3 swaps to make the array semi-ordered!

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. This is because the index() method needs to traverse the array to find the positions of elements 1 and n, which takes linear time in the worst case. Each index() call can potentially scan through all n elements, and we make two such calls.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variables n, i, j, and k, regardless of the input size. No additional data structures that scale with the input are created.

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

Common Pitfalls

1. Incorrectly Handling the Crossing Case

The most common mistake is forgetting to account for when elements 1 and n cross paths during swapping. When 1 starts to the right of n (i.e., position_of_one > position_of_n), they will inevitably pass each other as 1 moves left and n moves right.

Incorrect approach:

# Wrong: Always adding the distances without considering crossing
return position_of_one + (n - 1 - position_of_n)

Why it fails: This counts one swap twice when the elements cross. For example, with [2, 4, 1, 3], element 1 is at index 2 and element 4 is at index 1. Without the crossing adjustment, you'd calculate 2 + (4-1-1) = 4 swaps, but the actual answer is 3.

Correct approach:

# Check if elements will cross and adjust accordingly
if position_of_one > position_of_n:
    return position_of_one + (n - 1 - position_of_n) - 1
else:
    return position_of_one + (n - 1 - position_of_n)

2. Edge Case: Elements Already in Position

Another pitfall is not considering that 1 or n might already be in their target positions. While the formula handles this mathematically (returning 0 swaps for that element), explicitly checking can prevent confusion:

Example scenarios:

• If 1 is already at index 0: position_of_one = 0, contributing 0 swaps
• If n is already at index n-1: position_of_n = n-1, contributing 0 swaps
• If both are in position: the function should return 0

Solution: The current formula naturally handles these cases, but adding early return conditions can improve readability:

# Optional optimization for clarity
if position_of_one == 0 and position_of_n == n - 1:
    return 0

3. Misunderstanding Adjacent Swaps

Some might think they can directly swap non-adjacent elements or calculate Manhattan distance. Remember that only adjacent elements can be swapped, which is why we count the number of positions an element must move.

Wrong interpretation: Thinking you can swap 1 directly with any element to place it at index 0.

Correct understanding: Element 1 must be swapped with each adjacent element step by step until it reaches index 0, requiring exactly position_of_one swaps.