Semi-Ordered Permutation

Easy
1840.

Semi-Ordered Permutation

Semi-Ordered Permutation is an easy coding problem on arrays and simulation, asked in Amazon and Microsoft interviews.

nums is a permutation of the integers 1 to n (each appears exactly once). The permutation is semi-ordered when its first element is 1 and its last element is n.

In one operation you may swap any two adjacent elements. Return the minimum number of operations needed to make nums semi-ordered.

Example 1

Input
nums = [2,1,4,3]
Output
2
Explanation
Swap the first two elements to get [1,2,4,3], then the last two to get [1,2,3,4].

Example 2

Input
nums = [2,4,1,3]
Output
3
Explanation
Moving 1 to the front takes two swaps ([1,2,4,3]); moving 4 to the back takes one more.

Example 3

Input
nums = [1,3,4,2,5]
Output
0
Explanation
Already semi-ordered — the middle does not matter.

Constraints

  • 2 <= nums.length == n <= 50
  • 1 <= nums[i] <= 50
  • nums is a permutation of 1..n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var semiOrderedPermutation = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Semi-Ordered Permutation — Solution in Python, Java & C++

Semi-Ordered Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Semi-Ordered Permutation is an easy coding problem on arrays and simulation, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Simulation
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums is a permutation of the integers 1 to n (each appears exactly once). The permutation is semi-ordered when its first element is 1 and its last element is n.

In one operation you may swap any two adjacent elements. Return the minimum number of operations needed to make nums semi-ordered.

Example 1

Input: nums = [2,1,4,3]
Output: 2
Explanation: Swap the first two elements to get [1,2,4,3], then the last two to get [1,2,3,4].

Example 2

Input: nums = [2,4,1,3]
Output: 3
Explanation: Moving 1 to the front takes two swaps ([1,2,4,3]); moving 4 to the back takes one more.

Example 3

Input: nums = [1,3,4,2,5]
Output: 0
Explanation: Already semi-ordered — the middle does not matter.

Constraints

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

Hints for Semi-Ordered Permutation

  1. Hint 1

    Only two values matter: where 1 is and where n is.

  2. Hint 2

    Moving 1 from position i to the front costs i adjacent swaps; moving n from position j to the back costs n - 1 - j.

  3. Hint 3

    If 1 starts to the right of n, the two walks cross: one of the swaps moves both at once, so subtract one.

How to solve Semi-Ordered Permutation

The answer is the distance 1 has to travel left plus the distance n has to travel right, minus one when their paths cross, because a single swap of the adjacent pair (n, 1) advances both.

Approach

  1. Find i, the index of 1, and j, the index of n.
  2. The answer is i + (n - 1 - j).
  3. If i > j, subtract 1.

Why it works

Each adjacent swap moves 1 at most one place left and n at most one place right, so at least i swaps must touch 1 and at least n - 1 - j must touch n; only a swap of the two of them can count for both, and that happens at most once — exactly when 1 starts to the right of n. Bubbling 1 to the front and then n to the back achieves this bound.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Forgetting the crossing case over-counts by one ([2,4,1,3] needs 3, not 4).
  • Elements other than 1 and n never need to be put in order.

Reference solution

Python

from typing import List

def semiOrderedPermutation(nums: List[int]) -> int:
    n = len(nums)
    i = nums.index(1)
    j = nums.index(n)
    ops = i + (n - 1 - j)
    if i > j:
        ops -= 1
    return ops

Java

public static int semiOrderedPermutation(int[] nums) {
    int n = nums.length, i = 0, j = 0;
    for (int k = 0; k < n; k++) {
        if (nums[k] == 1) i = k;
        if (nums[k] == n) j = k;
    }
    int ops = i + (n - 1 - j);
    if (i > j) ops--;
    return ops;
}

C++

int semiOrderedPermutation(vector<int>& nums) {
    int n = nums.size(), i = 0, j = 0;
    for (int k = 0; k < n; k++) {
        if (nums[k] == 1) i = k;
        if (nums[k] == n) j = k;
    }
    int ops = i + (n - 1 - j);
    if (i > j) ops--;
    return ops;
}

JavaScript

var semiOrderedPermutation = function(nums) {
    var n = nums.length;
    var i = nums.indexOf(1), j = nums.indexOf(n);
    var ops = i + (n - 1 - j);
    if (i > j) ops--;
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays