Scale Engineer

Semi-Ordered Permutation

Easy
#2451Time: O(n). Finding the initial position of `1` takes O(n). The simulation loop for `1` runs O(n) times. Finding the position of `n` takes another O(n). The total time complexity is O(n) + O(n) + O(n) = O(n).Space: O(1) if the simulation is done in-place on the input array.
Data structures
Array

Prompt

You are given a 0-indexed permutation of n integers nums.

A permutation is called semi-ordered if the first number equals 1 and the last number equals n. You can perform the below operation as many times as you want until you make nums a semi-ordered permutation:

  • Pick two adjacent elements in nums, then swap them.

Return the minimum number of operations to make nums a semi-ordered permutation.

A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.

 

Example 1:

Input: nums = [2,1,4,3]
Output: 2
Explanation: We can make the permutation semi-ordered using these sequence of operations: 
1 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
2 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than two operations that make nums a semi-ordered permutation.

Example 2:

Input: nums = [2,4,1,3]
Output: 3
Explanation: We can make the permutation semi-ordered using these sequence of operations:
1 - swap i = 1 and j = 2. The permutation becomes [2,1,4,3].
2 - swap i = 0 and j = 1. The permutation becomes [1,2,4,3].
3 - swap i = 2 and j = 3. The permutation becomes [1,2,3,4].
It can be proved that there is no sequence of less than three operations that make nums a semi-ordered permutation.

Example 3:

Input: nums = [1,3,4,2,5]
Output: 0
Explanation: The permutation is already a semi-ordered permutation.

 

Constraints:

  • 2 <= nums.length == n <= 50
  • 1 <= nums[i] <= 50
  • nums is a permutation.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of moving the elements 1 and n to their target positions. It's an intuitive, greedy strategy. First, we focus on moving 1 to the beginning of the array (index 0) by repeatedly swapping it with its left neighbor. Then, in the modified array, we move n to the end (index n-1) by swapping it with its right neighbor. The total number of swaps is counted throughout this process.

Algorithm

  1. Initialize a counter swaps to 0.
  2. Get the length of the array, n.
  3. Phase 1: Move 1 to the front.
    • Find the index of 1, let's call it pos1.
    • In a loop, from i = pos1 down to 1, swap the element at i with the element at i-1.
    • Increment swaps for each swap.
  4. Phase 2: Move n to the end.
    • After 1 is at the front, find the new index of n, let's call it posn.
    • In a loop, from i = posn up to n-2, swap the element at i with the element at i+1.
    • Increment swaps for each swap.
  5. Return the total swaps.

Walkthrough

The algorithm works in two distinct phases:

  1. Move 1 to the front: We first iterate through the array to find the index of 1, let's call it pos1. The number of adjacent swaps required to move it to index 0 is exactly pos1. We simulate this by performing pos1 swaps, moving 1 leftward one step at a time. We add pos1 to our total swap count.

  2. Move n to the end: After 1 is in its correct place, the array is now different. We must find the new position of n. We iterate through the modified array to find n's index, posn. The number of swaps to move it to the end is (n - 1) - posn. We simulate these swaps and add this count to our total.

The final result is the sum of swaps from both phases.

class Solution {    public int semiOrderedPermutation(int[] nums) {        int n = nums.length;        int swaps = 0;         // Phase 1: Move 1 to the front        int pos1 = -1;        for (int i = 0; i < n; i++) {            if (nums[i] == 1) {                pos1 = i;                break;            }        }                // Simulate swapping 1 to the front        while (pos1 > 0) {            int temp = nums[pos1];            nums[pos1] = nums[pos1 - 1];            nums[pos1 - 1] = temp;            swaps++;            pos1--;        }         // Phase 2: Move n to the end        int posn = -1;        for (int i = 0; i < n; i++) {            if (nums[i] == n) {                posn = i;                break;            }        }                // The number of swaps for n is simply its distance from the end        swaps += (n - 1 - posn);                return swaps;    }}

Complexity

Time

O(n). Finding the initial position of `1` takes O(n). The simulation loop for `1` runs O(n) times. Finding the position of `n` takes another O(n). The total time complexity is O(n) + O(n) + O(n) = O(n).

Space

O(1) if the simulation is done in-place on the input array.

Trade-offs

Pros

  • The logic is straightforward and easy to follow.

  • It correctly solves the problem by breaking it down into two simpler subproblems.

Cons

  • Performs multiple passes over the array.

  • Involves modifying the input array, which might not be desirable.

  • Less efficient in terms of constant factors and actual operations compared to the analytical approach, although both have the same O(n) time complexity.

Solutions

class Solution {public  int semiOrderedPermutation(int[] nums) {    int n = nums.length;    int i = 0, j = 0;    for (int k = 0; k < n; ++k) {      if (nums[k] == 1) {        i = k;      }      if (nums[k] == n) {        j = k;      }    }    int k = i < j ? 1 : 2;    return i + n - j - k;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem