Minimum Operations to Sort a Permutation - Video Solutions

Problem Overview: You are given a permutation of numbers from 1..n. The task is to compute the minimum number of operations required to transform the array into sorted order. Since every value already belongs to a unique correct index, the problem reduces to identifying how elements are misplaced and how many operations are required to restore order.

Approach 1: Brute Force Swapping Simulation (O(n²) time, O(1) space)

Scan the array from left to right. Whenever the element at index i is not equal to i + 1, locate the correct value in the remaining part of the array and swap it into position. Each misplaced element may require a linear search to find its correct partner, which leads to O(n) work per position. This produces an overall O(n²) runtime but uses constant extra memory. The method is straightforward and helps visualize how elements move to their correct indices.

Approach 2: Cycle Decomposition (O(n) time, O(n) space)

A permutation can be viewed as a directed graph where each index points to the index where its value should go. Misplaced elements naturally form cycles. For a cycle of length k, exactly k - 1 swaps are required to place every element correctly. Traverse the array while tracking visited indices, follow each cycle until it closes, and accumulate cycleSize - 1 operations. Each element is visited once, giving O(n) time with O(n) space for the visited array. This interpretation treats the permutation as a set of independent components similar to problems involving graph traversal.

Approach 3: Greedy In‑Place Swapping (O(n) time, O(1) space)

You can eliminate the explicit visited structure by repeatedly placing elements directly into their correct positions. While nums[i] != i + 1, swap the current value with the element at its target index nums[i] - 1. Each swap places at least one element in its final position, so every index participates in at most one cycle resolution. The algorithm runs in O(n) time and constant space, similar to techniques used in greedy placement and array index mapping problems.

Recommended for interviews: Cycle decomposition is the clearest explanation. It shows you understand permutations as cycles and directly derives the k - 1 rule. Mention the brute force approach first to show baseline reasoning, then move to the linear-time cycle solution. If asked about space optimization, explain the in-place greedy swap variant.