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 <= 501 <= nums[i] <= 50nums is a permutation of 1..n
Hints for Semi-Ordered Permutation
Hint 1
Only two values matter: where
1is and wherenis.Hint 2
Moving
1from positionito the front costsiadjacent swaps; movingnfrom positionjto the back costsn - 1 - j.Hint 3
If
1starts to the right ofn, 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
- Find
i, the index of1, andj, the index ofn. - The answer is
i + (n - 1 - j). - If
i > j, subtract1.
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
1andnnever 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 opsJava
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