2717. Semi-Ordered Permutation
Problem Description
In this problem, we are given an array nums
which represents a permutation of n
integers. To recall, a permutation is a sequence containing each number from 1
to n
exactly once. The goal is to make this permutation semi-ordered using a specific operation. A permutation is said to be semi-ordered if the first element is 1
and the last element is n
. The operation we can perform is to swap any two adjacent elements, and we can do this as many times as necessary.
The task is to return the minimum number of such swap operations required to transform the given permutation into a semi-ordered permutation.
Intuition
To arrive at the solution, consider the fact that we only need to focus on the positions of the numbers 1
and n
in the permutation, because these are the elements that need to be at the start and end of the array, respectively.
Here's the step-by-step thought process:
-
Find the positions of
1
andn
in the array. These positions will determine the number of swap operations needed. -
If the number
1
is already at the start or the numbern
is already at the end of the array, no operations are needed for those numbers. Otherwise, we would need to swap each of them until they reach their correct positions. This can be calculated by the number of positions each needs to move. -
Since we can swap any two adjacent elements, we can independently move
1
to the start andn
to the end. -
If the initial position of
1
is before the position ofn
, we have an overlap situation when moving both1
andn
. Therefore, one operation that moves1
to the left also movesn
to the right, saving us one operation. -
Combining these observations, we can compute the minimum number of operations needed.
The intuition behind the algorithm is based on optimizing the process of arranging 1
at the start and n
at the end, by counting the movements without actually performing the swaps, and then subtracting the overlapping move if 1
comes before n
.
Solution Approach
The implementation of this solution involves a very straightforward approach without the need for any complicated data structures or algorithms. It follows directly from the observation that we only need to move 1
to the start and n
to the end of the array to achieve a semi-ordered permutation. The Python code provided does just that in a few steps:
-
Determine the length of the array
nums
to know how many elements we are dealing with, as this tells us the index of the last element in a zero-indexed array. -
Find the index of
1
in thenums
array using theindex
method, which will return the positioni
where1
is located. Similarly, find the index ofn
and store it in the variablej
. -
Calculate the number of operations needed to move
1
to the start of the array. This is simply the indexi
since1
needs to movei
places to the left to reach the starting position. -
Similarly, calculate the operations needed to move
n
to the end. The indexj
represents the position ofn
, and since it needs to move to the last position, we subtractj
from(n-1)
to find out how many placesn
needs to move right.n-1
is used because the array is zero-indexed. -
Using a conditional expression, we determine if
1
comes beforen
(i < j
). If so, there is one overlapping move when both1
andn
are moving towards their destined positions (since swapping to move1
to the start simultaneously movesn
closer to the end). In this case, one less operation (k
) is needed. -
Sum the operations needed to move
1
andn
, and subtract the overlapk
if there is any. This sum gives us the minimum number of operations required. -
Return this sum as the solution to the problem.
The pattern used here is mainly observation of the problem constraints and taking advantage of the properties of the permutation to find an efficient solution that runs in constant time, as it only involves index lookups and arithmetic operations.
The code doesn't use any complex algorithms or data structures because it doesn't perform the actual swap operations but rather calculates the moves needed based on the indexes of 1
and n
.
By following this simple logic, we achieve an optimal solution to the problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose the input array nums
is [4, 3, 2, 1, 5]
, which is a permutation of 5 integers. As per the problem, we need 1
at the start and 5
at the end in the fewest swaps possible.
Here's a step-by-step walkthrough:
-
Identify the initial positions of
1
and5
. Innums
,1
is at index 3 (i
) and5
is at index 4 (j
). Our task is to move1
to index 0 and5
to index 4 (since5
is already at the end, it stays in place). -
Since
1
is at index 3, it needsi = 3
swaps to reach the start of the array. -
For
5
, no swaps are needed since it is already at the last position,j = 4
. -
Check whether there's an overlap. Since
i < j
, there is no overlap because1
can move to the start without affecting the position of5
. -
Now, simply calculate the total number of swaps, which in our case would be the swaps needed for
1
, plus the swaps for5
(which are zero), minus any overlap (also zero in this case).We calculate swaps as follows:
- Swaps for
1
:i
(3 swaps) - Swaps for
5
:(n-1) - j
(0 swaps since 5 is already at the end) - Overlap:
k
(0 becausei < j
)
So, total swaps required:
3 + 0 - 0 = 3
- Swaps for
Therefore, we can transform the permutation [4, 3, 2, 1, 5]
into a semi-ordered permutation with a minimum of 3 swap operations:
Starting with: [4, 3, 2, 1, 5]
1st swap: [4, 3, 1, 2, 5]
2nd swap: [4, 1, 3, 2, 5]
3rd swap: [1, 4, 3, 2, 5]
The array is now semi-ordered, with 1
at the start and 5
at the end. We return 3 as the solution to the number of swaps needed.
Solution Implementation
1from typing import List
2
3class Solution:
4 def semiOrderedPermutation(self, nums: List[int]) -> int:
5 # Calculate the length of the input list
6 length_of_nums = len(nums)
7
8 # Find the index positions of the smallest and largest elements (1 and n)
9 index_of_min = nums.index(1)
10 index_of_max = nums.index(length_of_nums)
11
12 # Determine the correction factor based on the relative position of min and max
13 correction_factor = 1 if index_of_min < index_of_max else 2
14
15 # Calculate and return the result as per the given formula
16 result = index_of_min + length_of_nums - index_of_max - correction_factor
17 return result
18
1class Solution {
2 // Method to calculate the semi-ordered permutation value
3 public int semiOrderedPermutation(int[] nums) {
4 int length = nums.length; // Total number of elements in the array
5 int indexOne = 0; // Initialize the index of the element '1'
6 int indexN = 0; // Initialize the index of the element 'n', where 'n' is the length of the array
7
8 // Iterate through the array to find the indices of 1 and n
9 for (int k = 0; k < length; ++k) {
10 if (nums[k] == 1) {
11 indexOne = k; // Found the index of 1
12 }
13 if (nums[k] == length) {
14 indexN = k; // Found the index of the last element 'n'
15 }
16 }
17
18 // Determine the subtraction factor depending on the positions of 1 and n
19 int subtractionFactor = indexOne < indexN ? 1 : 2;
20
21 // Calculate and return the final semi-ordered permutation value
22 // by adding the position of 1, subtracting the position of n
23 // and then adjusting with the subtraction factor
24 return indexOne + length - indexN - subtractionFactor;
25 }
26}
27
1#include <vector>
2#include <algorithm> // Include algorithm library for std::find
3
4class Solution {
5public:
6 // Function to calculate the semi-ordered permutation count.
7 int semiOrderedPermutation(vector<int>& nums) {
8 int size = nums.size(); // Get the size of the nums vector
9 // Find the position (index) of the smallest element (1)
10 int indexMin = std::find(nums.begin(), nums.end(), 1) - nums.begin();
11 // Find the position (index) of the largest element (n)
12 int indexMax = std::find(nums.begin(), nums.end(), size) - nums.begin();
13
14 // Determine if smallest element comes before largest element
15 // if so, we use k = 1, if not k = 2 for the count adjustment
16 int k = (indexMin < indexMax) ? 1 : 2;
17
18 // Calculate the semi-ordered permutation count by subtracting
19 // the irrelevant elements using the indexes and k
20 return indexMin + size - indexMax - k;
21 }
22};
23
1function semiOrderedPermutation(nums: number[]): number {
2 // Get the length of the input array.
3 const length = nums.length;
4
5 // Find the index of the smallest element, which is 1.
6 const index1 = nums.indexOf(1);
7
8 // Find the index of the largest element, which is the length of the array.
9 const indexN = nums.indexOf(length);
10
11 // Determine if the smallest element's index is less than that of the largest.
12 // Choose 1 if smallest is before largest, otherwise 2.
13 const adjustmentFactor = index1 < indexN ? 1 : 2;
14
15 // Return the difference between the sum of indexes and the adjustment factor.
16 // This computes the gap between '1' and 'n', adjusting for inclusive/exclusive indexing.
17 return index1 + length - indexN - adjustmentFactor;
18}
19
Time and Space Complexity
The given Python function semiOrderedPermutation
calculates a result based on the positions of the smallest and largest elements in a list.
Time Complexity
The time complexity of the function is determined by the following operations:
n = len(nums)
ā Getting the length of the list, which is an O(1) operation.i = nums.index(1)
ā Finding the index of the element 1 in the list, which is an O(N) operation in the worst case, where N is the number of elements in the list.j = nums.index(n)
ā Finding the index of the largest element (which isn
), also an O(N) operation in the worst case.- The comparison
i < j
ā A simple comparison, which is an O(1) operation. - The last line is simple arithmetic and an assignment, all of which are O(1) operations.
The function contains no loops or recursive calls that depend on the size of the input list. The most time-consuming operations are the two index lookups, each of which is O(N). Therefore, the overall time complexity of the function is O(N), where N is the length of the input list nums
.
Space Complexity
The space complexity is determined by the additional memory used by the function:
- Variables
n
,i
,j
, andk
are all integers, each requiring a constant amount of space. - The function does not use any additional data structures that grow with the input size.
Hence, the space complexity of the function is O(1), which means it uses a constant amount of additional space regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!