3942. Minimum Operations to Sort a Permutation

MediumView on LeetCode

Array Math

Time: O(n)

Space: O(1)

Problem Overview

The only moves are reversing the whole array and rotating it one step to the left.

Intuition

The only moves are reversing the whole array and rotating it one step to the left. Both moves keep the cyclic order of the values, so the array can become 0, 1, ..., n - 1 only when walking away from 0 already produces that sequence, either clockwise or counterclockwise. Each direction has two ways to pay for the alignment: rotate until 0 is in place, or reverse, rotate, and reverse again. The answer is the cheaper of the directions that actually match, or -1 when neither does.

Algorithm

1Find the index of 0.
2Walk clockwise from that index and accept the direction when the values are exactly 0, 1, 2, and so on.
3If it matches, the cost is the minimum of the index itself and n minus that index plus 2.
4Walk counterclockwise the same way. If it matches, the cost is the minimum of the index plus 2 and n minus the index.
5Return the smaller accepted cost, or -1 when both walks fail.

Example Walkthrough

Input: nums = [1, 0, 2]

1.0 sits at index 1. Clockwise the next values are 2 then 1, which is not 0, 1, 2.
2.Counterclockwise the values are 0, then 1, then 2.
3.That direction costs min(1 + 2, 3 - 1) = 2. Reverse to [2, 0, 1], then rotate once to [0, 1, 2].

Output: 2

Common Pitfalls

•An already sorted array has 0 at index 0 and costs 0. Do not add a reverse.
•Both directions can be valid for n less than 3. Take the smaller cost.
•The walk must be exactly 0, 1, 2, ..., not merely nondecreasing with a gap.
•Simulating every rotate is too slow for n = 1e5. One pass in each direction is enough.

3942.cs

// Approach: Reverse and left-rotate preserve a cyclic order, so the array can
// become 0,1,...,n-1 only when walking from 0 is exactly that sequence in one
// direction. Find 0, then test the clockwise and counterclockwise orders.
// Clockwise costs min(rotations, reverse + rotations + reverse).
// Counterclockwise costs min(rotations + reverse, reverse + rotations).
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinOperations(int[] nums)
    {
        int n = nums.Length;
        int zero = 0;
        while (nums[zero] != 0)
            zero++;

        int ans = int.MaxValue;
        if (Matches(nums, zero, 1))
            ans = Math.Min(zero, n - zero + 2);
        if (Matches(nums, zero, -1))
            ans = Math.Min(ans, Math.Min(zero + 2, n - zero));
        return ans == int.MaxValue ? -1 : ans;
    }

    private static bool Matches(int[] nums, int zero, int step)
    {
        int n = nums.Length;
        int idx = zero;
        for (int value = 0; value < n; value++)
        {
            if (nums[idx] != value)
                return false;
            idx += step;
            if (idx == n)
                idx = 0;
            else if (idx < 0)
                idx = n - 1;
        }
        return true;
    }
}

Was this solution helpful?