3942. Minimum Operations to Sort a Permutation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums of length n, where nums is a permutation of the integers from 0 to n - 1.

You are allowed to perform only the following two operations:

Reverse the entire array. This flips the order of all elements, so the first element becomes the last, the second becomes the second-to-last, and so on.
Rotate Left by One: Move the first element to the end of the array, and shift all the remaining elements one position to the left.

Your task is to return the minimum number of operations needed to sort the array in increasing order. If sorting the array using only these operations is not possible, return -1.

In other words, by combining some sequence of full-array reversals and single left-rotations, you want to transform nums into the sorted sequence [0, 1, 2, ..., n - 1] using as few operations as possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Making the locally optimal choice at each step produces the globally optimal result.

Open in Flowchart

Intuition

The key observation is that the sorted array [0, 1, 2, ..., n - 1] always starts with 0. So no matter how we manipulate the array, 0 must eventually end up at the front. This makes the position of 0 in the original array, which we call zero, the natural anchor point for our reasoning.

Now, think about what the two operations actually do:

A left-rotation keeps the relative circular order of the elements unchanged; it only shifts where the sequence "begins". So if the array is already in increasing order when read circularly starting from 0, we just need to rotate enough times to bring 0 to the front.
A reversal flips the entire order. After reversing, an array that was increasing becomes decreasing, and vice versa.

This tells us there are only two meaningful "shapes" the array can have for it to be sortable:

Reading from 0 and moving to the right (with wrap-around), the values increase: 0, 1, 2, .... This is the natural circular increasing order.
Reading from 0 and moving to the left (with wrap-around), the values increase. This is the increasing order seen in reverse, meaning the array is essentially a reversed-and-rotated version of the sorted array.

If neither of these holds, then no combination of rotations and reversals can ever sort the array, so the answer is -1. This is exactly what the check(1) and check(-1) functions test: check(1) verifies the increasing order going right from 0, and check(-1) verifies it going left from 0.

Once we know which shape we have, we count the operations for each valid way to reach the sorted array:

If it is increasing to the right from 0:
- We can simply left-rotate zero times to push 0 to the front. Cost: zero.
- Or we can reverse first (1 op), left-rotate n - zero times, then reverse again (1 op). Cost: n - zero + 2.
If it is increasing to the left from 0:
- We can left-rotate zero + 1 times to move 0 to the end, then reverse once. Cost: zero + 2.
- Or we can reverse first (1 op), then left-rotate n - zero - 1 times to bring 0 to the front. Cost: n - zero.

Since rotating directly and rotating after a reversal cover the array from "both ends", trying all four candidate methods and taking the minimum guarantees we find the cheapest path. If no method applies, we return -1.

Solution Approach

We use case analysis to enumerate the limited number of ways the array can be sorted, then pick the cheapest one.

Step 1: Locate 0.

We first find the index of 0 in the array using nums.index(0), storing it as zero. This is our anchor, since 0 must end up at the front of the sorted array.

Step 2: Check the two possible orderings.

We define a helper function check(step) that verifies whether the array is increasing when we walk through it starting from zero with a given direction:

step = 1 means we move to the right (with wrap-around) from 0.
step = -1 means we move to the left (with wrap-around) from 0.

Inside check, we iterate i from 1 to n - 1 and compare consecutive elements along the chosen direction:

prev = (zero + (i - 1) * step) % n
curr = (zero + i * step) % n
if nums[prev] > nums[curr]:
    return False

The modulo % n handles the circular wrap-around. If every consecutive pair is in increasing order, the array follows that shape and check returns True.

Step 3: Compute the cost for each valid method.

We initialize ans = inf to track the minimum number of operations.

If check(1) is True (increasing to the right from 0):

Rotate directly: left-rotate zero times to bring 0 to the front. Cost: zero.
Reverse, rotate, reverse back: cost n - zero + 2 (the +2 accounts for the two reversals).

if check(1):
    ans = min(ans, zero)
    ans = min(ans, n - zero + 2)

If check(-1) is True (increasing to the left from 0):

Rotate then reverse: left-rotate zero + 1 times to move 0 to the end, then reverse once. Cost: zero + 2.
Reverse then rotate: reverse first, then left-rotate n - zero - 1 times. Cost: n - zero.

if check(-1):
    ans = min(ans, zero + 2)
    ans = min(ans, n - zero)

Step 4: Return the answer.

If ans is still inf, neither ordering applied, so sorting is impossible and we return -1. Otherwise, we return the minimum cost found:

return -1 if ans == inf else ans

Complexity Analysis:

Time complexity: O(n). Finding the index of 0 takes O(n), and each check call scans the array once in O(n). There are a constant number of check calls.
Space complexity: O(1). We only use a few variables and perform no extra allocation.

This approach is efficient because, despite the operations seemingly allowing many combinations, only a constant number of meaningful transformations exist. We simply enumerate all four candidates and take the minimum.

Example Walkthrough

Let's trace through the solution with a small example: nums = [3, 4, 0, 1, 2], so n = 5.

The sorted target is [0, 1, 2, 3, 4].

Step 1: Locate 0.

Scanning the array, 0 sits at index 2, so zero = 2.

index:  0  1  2  3  4
nums:  [3, 4, 0, 1, 2]
              ^
            zero = 2

Step 2: Check the two possible orderings.

We test check(1) — walking right from zero with wrap-around:

Starting at index 2, the circular right-walk visits:

idx 2 -> 3 -> 4 -> 0 -> 1
val 0 -> 1 -> 2 -> 3 -> 4

Each consecutive pair is increasing (0 < 1 < 2 < 3 < 4), so check(1) returns True. This is the natural circular increasing order — the array is just the sorted sequence rotated.

We could also test check(-1) (walking left), but since check(1) already holds, this shape is confirmed.

Step 3: Compute the cost for each valid method.

Since check(1) is True, two candidate methods apply:

Rotate directly: left-rotate zero = 2 times to push 0 to the front.

start:        [3, 4, 0, 1, 2]
rotate once:  [4, 0, 1, 2, 3]
rotate twice: [0, 1, 2, 3, 4]   ✓ sorted!

Cost = zero = 2.

Reverse, rotate, reverse back: cost = n - zero + 2 = 5 - 2 + 2 = 5.

reverse:           [2, 1, 0, 4, 3]   (1 op)
rotate (n - zero)
 = 3 times:        [4, 3, 2, 1, 0]   (3 ops)
reverse again:     [0, 1, 2, 3, 4]   (1 op) ✓ sorted!

Total = 1 + 3 + 1 = 5.

We take the minimum: ans = min(2, 5) = 2.

Step 4: Return the answer.

ans = 2, which is not inf, so the answer is 2.

This matches our direct trace: just two left-rotations transform [3, 4, 0, 1, 2] into [0, 1, 2, 3, 4]. The solution avoids simulating every possible sequence by recognizing that only a constant number of meaningful transformations exist, then picking the cheapest valid one.

Solution Implementation

1from typing import List
2from math import inf
3
4
5class Solution:
6    def minOperations(self, nums: List[int]) -> int:
7        # Total number of elements in the array.
8        n = len(nums)
9
10        # Find the index of the single zero in the array.
11        zero_index = nums.index(0)
12
13        def is_sorted_with_step(step: int) -> bool:
14            """
15            Check whether traversing the array starting from `zero_index`
16            with the given circular `step` produces a non-decreasing sequence.
17
18            Each position is computed modulo n to wrap around the array,
19            simulating a circular traversal in either direction.
20            """
21            for i in range(1, n):
22                # Previous position in the circular traversal.
23                prev_pos = (zero_index + (i - 1) * step) % n
24                # Current position in the circular traversal.
25                curr_pos = (zero_index + i * step) % n
26
27                # If order is violated, the step direction is invalid.
28                if nums[prev_pos] > nums[curr_pos]:
29                    return False
30
31            return True
32
33        # Track the minimum number of operations found so far.
34        answer = inf
35
36        # Case 1: traversal in the forward direction (step = +1).
37        if is_sorted_with_step(1):
38            # Option A: rotate so the zero moves to the front directly.
39            answer = min(answer, zero_index)
40            # Option B: account for the wrap-around cost.
41            answer = min(answer, n - zero_index + 2)
42
43        # Case 2: traversal in the backward direction (step = -1).
44        if is_sorted_with_step(-1):
45            # Option A: cost considering the offset from the front.
46            answer = min(answer, zero_index + 2)
47            # Option B: rotate so the zero aligns from the back.
48            answer = min(answer, n - zero_index)
49
50        # If no valid arrangement was found, return -1.
51        return -1 if answer == inf else answer
52

1import java.util.function.IntPredicate;
2
3class Solution {
4    public int minOperations(int[] nums) {
5        int length = nums.length;
6
7        // Locate the index of the element whose value is 0,
8        // which serves as the starting anchor point.
9        int zeroIndex = 0;
10        for (int i = 0; i < length; i++) {
11            if (nums[i] == 0) {
12                zeroIndex = i;
13                break;
14            }
15        }
16
17        // Effectively final copy needed for use inside the lambda.
18        final int anchorIndex = zeroIndex;
19
20        // Predicate that verifies whether, starting from the anchor and
21        // walking in the given direction (step), the array is non-decreasing.
22        // The traversal wraps around using modular arithmetic so the array
23        // is treated as circular.
24        IntPredicate isNonDecreasing = step -> {
25            for (int i = 1; i < length; i++) {
26                // Index of the previous element along the chosen direction.
27                int prevIndex = (anchorIndex + (i - 1) * step + length) % length;
28                // Index of the current element along the chosen direction.
29                int currIndex = (anchorIndex + i * step + length) % length;
30
31                // If the order breaks, the sequence is not sorted in this direction.
32                if (nums[prevIndex] > nums[currIndex]) {
33                    return false;
34                }
35            }
36
37            return true;
38        };
39
40        int answer = Integer.MAX_VALUE;
41
42        // Check the forward (step = +1) direction.
43        if (isNonDecreasing.test(1)) {
44            // Cost of shifting so the anchor reaches its target one way.
45            answer = Math.min(answer, zeroIndex);
46            // Cost of shifting in the complementary direction.
47            answer = Math.min(answer, length - zeroIndex + 2);
48        }
49
50        // Check the backward (step = -1) direction.
51        if (isNonDecreasing.test(-1)) {
52            // Cost of shifting so the anchor reaches its target one way.
53            answer = Math.min(answer, zeroIndex + 2);
54            // Cost of shifting in the complementary direction.
55            answer = Math.min(answer, length - zeroIndex);
56        }
57
58        // If no valid arrangement was found, return -1.
59        return answer == Integer.MAX_VALUE ? -1 : answer;
60    }
61}
62

1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        int n = nums.size();
5
6        // Locate the index of the element 0 (the smallest value, treated as the cycle's start).
7        int zeroIndex = ranges::find(nums, 0) - nums.begin();
8
9        // Check whether starting from zeroIndex and moving with the given step
10        // produces a non-decreasing sequence around the circular array.
11        auto isNonDecreasing = [&](int step) -> bool {
12            for (int i = 1; i < n; i++) {
13                // Previous position in the circular traversal.
14                int prevIndex = (zeroIndex + (i - 1) * step + n) % n;
15                // Current position in the circular traversal.
16                int currIndex = (zeroIndex + i * step + n) % n;
17
18                // If the order breaks, this direction is not valid.
19                if (nums[prevIndex] > nums[currIndex]) {
20                    return false;
21                }
22            }
23            return true;
24        };
25
26        int ans = INT_MAX;
27
28        // Case 1: traverse forward (step = +1).
29        // Either pop from the left zeroIndex times,
30        // or pop from the right while keeping a sorted prefix.
31        if (isNonDecreasing(1)) {
32            ans = min(ans, zeroIndex);
33            ans = min(ans, n - zeroIndex + 2);
34        }
35
36        // Case 2: traverse backward (step = -1).
37        // Either pop from the left side or from the right side accordingly.
38        if (isNonDecreasing(-1)) {
39            ans = min(ans, zeroIndex + 2);
40            ans = min(ans, n - zeroIndex);
41        }
42
43        // If no valid arrangement was found, return -1.
44        return ans == INT_MAX ? -1 : ans;
45    }
46};
47

1/**
2 * Finds the minimum number of operations to make the array sorted,
3 * where operations involve traversing the array in a circular manner
4 * starting from the position of the zero element.
5 *
6 * @param nums - The input array containing exactly one zero
7 * @returns The minimum number of operations, or -1 if impossible
8 */
9function minOperations(nums: number[]): number {
10    // Total number of elements in the array
11    const n: number = nums.length;
12
13    // Locate the index of the single zero element, used as the traversal anchor
14    const zeroIndex: number = nums.indexOf(0);
15
16    /**
17     * Checks whether traversing the array circularly with a given step
18     * direction produces a non-decreasing sequence.
19     *
20     * @param step - The direction/step of traversal (e.g. 1 for forward, -1 for backward)
21     * @returns True if the sequence is non-decreasing, otherwise false
22     */
23    const check = (step: number): boolean => {
24        for (let i = 1; i < n; i++) {
25            // Compute the previous index in the circular traversal
26            const prevIndex: number = (zeroIndex + (i - 1) * step + n) % n;
27
28            // Compute the current index in the circular traversal
29            const currIndex: number = (zeroIndex + i * step + n) % n;
30
31            // If the order is violated, this direction is invalid
32            if (nums[prevIndex] > nums[currIndex]) {
33                return false;
34            }
35        }
36
37        return true;
38    };
39
40    // Initialize the answer to the largest safe integer for comparison
41    let ans: number = Number.MAX_SAFE_INTEGER;
42
43    // Try traversing in the forward direction (step = 1)
44    if (check(1)) {
45        // Cost when moving directly from the zero index
46        ans = Math.min(ans, zeroIndex);
47        // Cost when wrapping around the array
48        ans = Math.min(ans, n - zeroIndex + 2);
49    }
50
51    // Try traversing in the backward direction (step = -1)
52    if (check(-1)) {
53        // Cost when wrapping around the array
54        ans = Math.min(ans, zeroIndex + 2);
55        // Cost when moving directly from the zero index
56        ans = Math.min(ans, n - zeroIndex);
57    }
58
59    // If no valid direction was found, return -1; otherwise return the minimum cost
60    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
61}
62

Time and Space Complexity

Time complexity: O(n), where n is the length of the array nums. Finding the index of 0 via nums.index(0) takes O(n) time. The check function iterates over the array once, performing constant-time operations (modular arithmetic and comparisons) per iteration, so each call costs O(n). Since check is invoked a constant number of times (twice, for step 1 and step -1), the overall time complexity remains O(n).
Space complexity: O(1). Only a constant number of auxiliary variables (n, zero, prev, curr, ans, step, i) are used, regardless of the input size. No additional data structures that scale with n are created.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting the edge cases when `zero_index == 0`

The most subtle bug in this solution is that when 0 is already at the front of the array, several of the four cost formulas become inconsistent or count phantom operations.

Consider an already-sorted array like nums = [0, 1, 2, 3]. Here zero_index = 0:

is_sorted_with_step(1) returns True (it's increasing to the right).
Option A gives answer = zero_index = 0. ✅ Correct — no operations needed.

But now look at is_sorted_with_step(-1). Walking left from index 0 visits nums[0], nums[3], nums[2], nums[1] = 0, 3, 2, 1, which is not increasing, so check(-1) is False. Good — but this is luck, not design.

The real trap appears when both check(1) and check(-1) can be True simultaneously, which happens for arrays of length 1 or 2:

nums = [0, 1]   # n = 2, zero_index = 0

check(1): compares nums[0]=0 and nums[1]=1 → increasing → True.
check(-1): compares nums[0]=0 and nums[(0-1)%2]=nums[1]=1 → 0 <= 1 → True.

Both pass! The candidate costs become:

Formula	Value
`zero_index`	`0` ✅
`n - zero_index + 2`	`4`
`zero_index + 2`	`2`
`n - zero_index`	`2`

The min still produces the correct answer 0 here because Option A of Case 1 dominates. However, the formulas zero_index + 2 and n - zero_index + 2 can produce values that appear valid but correspond to operation sequences that don't actually re-sort the array — they happen to be overridden by a cheaper, correct option. The code is correct because it takes the minimum, but it is fragile: any reordering of the logic or a tweak to one formula could surface an invalid-but-cheap candidate.

Pitfall 2: Off-by-one in the "rotate to back then reverse" cost

A frequent mistake when re-deriving these formulas by hand is to write the backward-direction costs as zero_index + 1 (just the rotations) instead of zero_index + 2 (rotations plus the final reverse). Forgetting to add the cost of the reversal operation itself silently undercounts:

# WRONG: forgets the reverse operation
answer = min(answer, zero_index + 1)
# RIGHT:
answer = min(answer, zero_index + 2)

Pitfall 3: Assuming `-1` cases never occur for permutations

Because nums is guaranteed to be a permutation, it is tempting to believe a solution always exists. This is false. Example:

nums = [1, 0, 2]   # n = 3

zero_index = 1.
check(1): walk right from index 1 → nums[1]=0, nums[2]=2, nums[0]=1 → 0,2,1 → 2 > 1 → False.
check(-1): walk left from index 1 → nums[1]=0, nums[0]=1, nums[2]=2 → 0,1,2 → increasing → True!

So this one is solvable, but it demonstrates that you cannot assume forward-direction success. An array like [2, 0, 1] reversed/rotated may still fail both checks, and the -1 branch is genuinely reachable. Dropping the -1 return (assuming permutations are always sortable) is a real correctness bug.

Solution / How to Guard Against These Pitfalls

1. Add explicit small-n handling and an assertion-style sanity check.

For n <= 1, the array is trivially sorted; return 0 immediately to avoid relying on the formulas:

if n <= 1:
    return 0

2. Verify each candidate by simulation instead of trusting raw formulas.

The most robust defense is to simulate the proposed operation sequence and confirm it actually produces the sorted array before accepting its cost. This eliminates the fragility from Pitfall 1:

def simulate_cost(rotations: int, reverses_before: int, reverse_after: bool) -> float:
    arr = nums[:]
    if reverses_before:
        arr.reverse()
    arr = arr[rotations:] + arr[:rotations]
    if reverse_after:
        arr.reverse()
    cost = rotations + reverses_before + (1 if reverse_after else 0)
    return cost if arr == sorted(arr) else inf

Then take the minimum over the four candidate plans. This is O(n) per candidate and a constant number of candidates, so it preserves overall O(n) time while making the logic self-validating.

3. Always keep the -1 fallthrough.

Never remove the final guard:

return -1 if answer == inf else answer

This correctly handles permutations such as [2, 0, 1] or larger scrambles where neither circular ordering is monotonic, ensuring impossible cases are reported rather than returning a bogus minimal cost.

By combining explicit edge-case handling, simulation-based validation, and a preserved -1 fallthrough, the solution becomes both correct and resilient to the off-by-one and "always-solvable" assumptions that commonly trip people up.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know