2717. Semi-Ordered Permutation LeetCode Solution

In this guide, you will get 2717. Semi-Ordered Permutation LeetCode Solution with the best time and space complexity. The solution to Semi-Ordered Permutation problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Semi-Ordered Permutation solution in C++
Semi-Ordered Permutation solution in Java
Semi-Ordered Permutation solution in Python
Additional Resources

2717. Semi-Ordered Permutation LeetCode Solution image

Problem Statement of Semi-Ordered Permutation

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.

Complexity Analysis

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

2717. Semi-Ordered Permutation LeetCode Solution in C++

class Solution {
 public:
  int semiOrderedPermutation(vector<int>& nums) {
    const int n = nums.size();
    const int index1 = find(nums.begin(), nums.end(), 1) - nums.begin();
    const int indexN = find(nums.begin(), nums.end(), n) - nums.begin();
    return index1 + (n - 1 - indexN) - (index1 > indexN ? 1 : 0);
  }
};
/* code provided by PROGIEZ */

2717. Semi-Ordered Permutation LeetCode Solution in Java

class Solution {
  public int semiOrderedPermutation(int[] nums) {
    final int n = nums.length;
    int index1 = -1;
    int indexN = -1;
    for (int i = 0; i < nums.length; ++i) {
      if (nums[i] == 1)
        index1 = i;
      else if (nums[i] == n)
        indexN = i;
    }
    return index1 + (n - 1 - indexN) - (index1 > indexN ? 1 : 0);
  }
}
// code provided by PROGIEZ

2717. Semi-Ordered Permutation LeetCode Solution in Python

class Solution:
  def semiOrderedPermutation(self, nums: list[int]) -> int:
    n = len(nums)
    index1 = nums.index(1)
    indexN = nums.index(n)
    return index1 + (n - 1 - indexN) - int(index1 > indexN)
 # code by PROGIEZ