Skip to main content
Talentd

Sort Array Using Prefix Reversals - Solution & Explanation

MediumPremiumFree on FleetCode10 min read
Practice this problem

Problem Statement

You are given an integer array nums of length n, where nums is a permutation of the integers in the range [0, n - 1].

You are also given an integer array pre, where each pre[i] is a valid prefix length.

In one operation, you may choose any length x from pre and reverse the first x elements of nums.

For example, applying a prefix reversal of length 3 on [4, 1, 2, 3] results in [2, 1, 4, 3].

Return the minimum number of operations required to sort nums in ascending order. If it is impossible to sort nums, return -1.

 

Example 1:

Input: nums = [2,0,1], pre = [2,3]

Output: 2

Explanation:

  • Reverse pre[1] = 3 elements to get nums = [1, 0, 2].
  • Then reverse pre[0] = 2 elements to get nums = [0, 1, 2].
  • Thus, the minimum number of prefix reversal required is 2.

Example 2:

Input: nums = [1,0,2], pre = [1,3]

Output: -1

Explanation:

It is impossible to sort the array using the given prefix lengths, so the answer is -1.

Example 3:

Input: nums = [0,1], pre = [2]

Output: 0

Explanation:

Since nums is already sorted, no prefix reversals are needed. Thus, the answer is 0.

 

Constraints:

  • 1 <= n == nums.length <= 8
  • 0 <= nums[i] <= n - 1
  • 1 <= pre.length <= n
  • 1 <= pre[i] <= n
  • ​​​​​​​nums is a permutation of integers from 0 to n - 1.
  • pre consists of unique integers.

Approach Overview

Problem Overview: You need to sort an array using only prefix reversals. A prefix reversal flips the first k elements of the array. The challenge is finding a sequence of flips that produces a sorted array efficiently.

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

The brute force idea tries multiple prefix reversals at each position until the array becomes sorted. You repeatedly scan the array, identify misplaced elements, and test flips that move values closer to their target positions. This works for small inputs but wastes time because every flip may require another full scan to validate ordering. Use this approach only to understand how prefix reversals affect array state.

Approach 2: Greedy Pancake Sort (O(n²) time, O(1) space)

This is the standard and expected solution. Iterate from the end of the array toward the beginning. For each index, locate the maximum element in the unsorted portion, reverse its prefix to bring it to the front, then reverse the larger prefix to move it into its final sorted position. Each iteration fixes exactly one element, which keeps the logic simple and deterministic. This approach is commonly categorized under greedy and array problems because every operation greedily places the next largest value.

Approach 3: Optimized Greedy with Early Skip (O(n²) time, O(1) space)

You can reduce unnecessary reversals by skipping elements already positioned correctly. Before performing any flip, check whether the current maximum already sits at its target index. If it does, continue immediately to the next iteration. This does not improve worst-case complexity, but it reduces operations significantly on partially sorted arrays. Interviewers often appreciate this refinement because it shows attention to practical optimization instead of only asymptotic analysis.

Recommended for interviews: Interviewers expect the greedy pancake sort solution because it directly matches the constraints of prefix reversals. Showing the brute force idea first demonstrates problem exploration, but the greedy method proves you can identify the invariant: after every two reversals, one element reaches its final position. Understanding prefix operations and in-place manipulation also overlaps with sorting interview patterns.

Solution

Since n \le 8, the number of permutations is at most 8! = 40320, so we can use BFS to find the minimum number of operations.

Treat the current array as a state, and the target state is [0, 1, ldots, n - 1]. If the initial state is already the target, return 0. Otherwise, start BFS from the initial state: each time take a state from the queue, enumerate every prefix length x in pre, and reverse the first x elements to obtain a new state. If the new state equals the target, return the current number of steps; otherwise, if it has not been visited, enqueue it. If the search finishes without reaching the target, return -1.

For convenience of deduplication, encode each permutation as an integer in base 8 (every element lies in [0, 7]).

The time complexity is O(n! cdot m cdot n), and the space complexity is O(n! cdot n). Here, n is the length of the array, and m is the length of pre.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n³)O(1)Learning how prefix reversals affect ordering
Greedy Pancake SortO(n²)O(1)General case and interview settings
Optimized Greedy with Early SkipO(n²)O(1)Partially sorted arrays with fewer flips

Frequently Asked Questions

Is Sort Array Using Prefix Reversals easy or hard?
Sort Array Using Prefix Reversals is usually considered a medium-level problem. The implementation is straightforward once you identify the greedy strategy, but recognizing the correct sequence of flips can take practice.
Sort Array Using Prefix Reversals Python/Java solution
Python solutions typically use slicing or two-pointer reversal helpers, while Java implementations rely on manual swapping inside a reverse function. Both versions implement the same greedy pancake sort logic with O(n²) time complexity.
How to solve Sort Array Using Prefix Reversals in O(n)?
An O(n) solution is not generally achievable for arbitrary arrays using only prefix reversals because locating and repositioning elements requires repeated scans and flips. The accepted interview solution is the O(n²) greedy pancake sort algorithm.
What is the best approach for Sort Array Using Prefix Reversals?
The greedy pancake sort approach is the standard solution. It repeatedly places the largest unsorted element into its final position using at most two prefix reversals. The algorithm runs in O(n²) time with O(1) extra space.
Is Sort Array Using Prefix Reversals asked at Google/Amazon/Meta?
Prefix reversal and pancake sorting problems appear in coding interviews focused on greedy algorithms, array manipulation, and in-place operations. Variants of this problem have been discussed in interviews at large companies including Google, Amazon, and Meta.
What data structure is used in Sort Array Using Prefix Reversals?
The problem mainly uses arrays with in-place reversal operations. No advanced data structures are required, although careful index manipulation is necessary to perform efficient prefix flips.
What is the time complexity of Sort Array Using Prefix Reversals?
The optimal practical solution runs in O(n²) time because each iteration scans the unsorted section to locate the maximum element and performs prefix reversals. Space complexity stays O(1) since all operations are done in place.

Ready to solve this problem?

Practice Sort Array Using Prefix Reversals with our built-in code editor and test cases.

Practice on FleetCode