0

Sort an array with rotate and flip operations

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Sort an array with rotate and flip operations

Companies: Amazon

Difficulty: Hard

Problem statement

You are given an array arr of n distinct integers. You may apply two operations, and each one counts as one step:

  • Rotate: remove the first element and append it to the end. [p, q, r, s] becomes [q, r, s, p].
  • Flip: reverse the whole array. [p, q, r, s] becomes [s, r, q, p].

Return the minimum number of steps needed to make arr strictly increasing. If no sequence of steps sorts it, return -1.

Implement min_ops(arr: list[int]) -> int.

Constraints

  • 1 <= n <= 10^5
  • All values are distinct and fit in a 32-bit signed integer.
  • Aim for O(n log n) time or better.

Example 1

Input:  arr = [30, 40, 10, 20]
Output: 2

Rotate twice: [40, 10, 20, 30], then [10, 20, 30, 40].

Example 2

Input:  arr = [20, 30, 40, 50, 10]
Output: 3

Four rotations work, but flip, rotate, flip is shorter: [10, 50, 40, 30, 20], [50, 40, 30, 20, 10], [10, 20, 30, 40, 50].

Example 3

Input:  arr = [5, 1, 3, 2]
Output: -1

Approach

Brute force. Treat every arrangement as a node and each operation as an edge, then BFS from the input until the sorted array appears. Each node is a full array (O(n) to copy and hash), so this works but costs O(n²) at best, and it needs an argument for why the graph stays small. That argument is the key insight.

Key insight: only 2n arrangements are reachable. Put the elements on a circle in their original order. Rotate turns the circle by one position; flip reads it in the opposite direction. Neither operation ever changes which elements are neighbours on the circle. So every reachable array is "start at index s, walk in direction d", with s in 0..n-1 and d in {+1, -1}. That is at most 2n states (the dihedral group), and each state is a pair (s, d), not an array.

In that representation:

  • Rotate: (s, d) -> (s + d, d). The next element in the walk becomes the first one.
  • Flip: (s, d) -> (s + (n-1)·d, -d). The old last element becomes the first, and the direction reverses.

Is sorting possible? The sorted array is reachable only if some (s, d) reads the input in ascending order. The start must be the index of the minimum. Try d = +1 and d = -1 and check the walk against the sorted ranks in O(n). If neither works, return -1.

Minimum cost. BFS over the 2n (s, d) states from (0, +1) gives the answer in O(n) and is easy to defend in an interview. You can also price the target (t, d) directly:

  • d = +1 (forward orientation): rotate t times, or go the other way round with flip, rotate (n - t) times, flip, because flip · rotate^j · flip rotates right by j. Cost min(t, n - t + 2), or 0 when t = 0.
  • d = -1 (reversed orientation): exactly one flip. Rotate before it (k = t + 1 rotations) or after it (j = n - 1 - t rotations), all mod n. Cost 1 + min((t + 1) mod n, (n - 1 - t) mod n).

A common mistake is to answer the forward case with t alone. For [20, 30, 40, 50, 10], four rotations work, but flip-rotate-flip takes only 3.

Invariant: after any sequence of operations, the array is the cyclic walk of the original from some (s, d). Cyclic adjacency is never broken, which is why the state space is 2n and why the -1 check is exact.

n = 1 needs 0 operations. When n = 2, a rotate and a flip have the same effect, so the answer is 0 or 1.

Code

from __future__ import annotations
from collections import deque


def find_target(arr: list[int]) -> tuple[int, int] | None:
    """Return (start, direction) such that reading arr cyclically from
    `start` in `direction` (+1 or -1) gives ascending order, or None."""
    n = len(arr)
    if n == 1:
        return (0, 1)
    s = arr.index(min(arr))
    rank = {v: i for i, v in enumerate(sorted(arr))}
    for d in (1, -1):
        if all(rank[arr[(s + i * d) % n]] == i for i in range(n)):
            return (s, d)
    return None


def min_ops_bfs(arr: list[int]) -> int:
    """BFS over the 2n dihedral states (start, direction). O(n)."""
    n = len(arr)
    target = find_target(arr)
    if target is None:
        return -1
    start = (0, 1)
    dist = {start: 0}
    queue = deque([start])
    while queue:
        state = queue.popleft()
        if state == target:
            return dist[state]
        s, d = state
        rotated = ((s + d) % n, d)                 # first element -> end
        flipped = ((s + (n - 1) * d) % n, -d)      # last element becomes first
        for nxt in (rotated, flipped):
            if nxt not in dist:
                dist[nxt] = dist[state] + 1
                queue.append(nxt)
    return -1  # unreachable for a valid target, kept for safety


def min_ops(arr: list[int]) -> int:
    """Closed form. O(n) to find the target, O(1) to price it."""
    n = len(arr)
    target = find_target(arr)
    if target is None:
        return -1
    if n <= 2:
        return target[0] if n == 2 else 0  # n == 2: one rotate == one flip
    t, d = target
    if d == 1:
        # rotate left t times, or flip, rotate n - t times the other way, flip
        return min(t, (n - t) % n + 2) if t else 0
    # one flip, placed after k rotations (k = t + 1) or before j rotations
    return 1 + min((t + 1) % n, (n - 1 - t) % n)

min_ops_bfs is the version to write first. min_ops is the O(1)-after-detection refinement, checked against a brute-force BFS over real arrays for every permutation with n ≤ 7.

Complexity

  • Detecting the target (s, d): O(n log n) time for the sorted ranks, or O(n) if values are already a permutation of 0..n-1. O(n) space for the rank map.
  • BFS over states: O(n) time and O(n) space (2n states, two edges each).
  • Closed form after detection: O(1) time and space.
  • Brute force over full arrays: O(n²) time and space. Do not ship it, but it is a good test oracle.

Test cases

  • [30, 40, 10, 20] → 2 (rotate, rotate).
  • [10, 20, 30] → 0 (already sorted).
  • [10, 50, 40, 30, 20] → 2 (rotate gives [50, 40, 30, 20, 10], then flip).
  • [50, 40, 30, 20, 10] → 1 (one flip).
  • [20, 30, 40, 50, 10] → 3 (flip, rotate, flip), which beats four rotations.
  • [5, 1, 3, 2] → -1 (1 and 3 are adjacent on the circle but not in sorted order).
  • [7] → 0. [2, 1] → 1.
  • [2, 1, 3] → 2. With n = 3, all six orders are reachable.
  • Large input, n = 10^5, a rotation of sorted by n/2: about n/2 (closed form), computed in linear time.

Follow-ups

  1. Return the operations, not just the count. Keep a parent pointer per (s, d) state in the BFS and walk back from the target, or emit the closed form's recipe (R^t, F R^j F, R^k F or F R^j).
  2. Different costs per operation (for example, flip costs c). The state graph is unchanged, so use Dijkstra on 2n states, or compare the same few candidate shapes with weighted costs: t, 2c + (n - t), k + c, c + j.
  3. Duplicates allowed. The rank check becomes "non-decreasing". Several starts may now be valid, so try every index where the walk begins a non-decreasing cyclic run and take the minimum cost. That is still O(n) candidates with an O(1) price each after an O(n) scan.
  4. Rotate in both directions, or flip only a prefix. Two-way rotation makes the forward cost min(t, n - t). A prefix flip (pancake sort) breaks the 2n-state argument completely: the state space becomes n!, and you are into BFS or IDA* on permutations, which only works for small n.
  5. Many queries on a stream of arrays. Detection is the bottleneck. Reuse the sort with counting when values are bounded, and keep the O(1) pricing.

Interviewer expectations

Mid-level (L4)

  • Simulates the operations correctly and proposes BFS over arrays.
  • Finds the -1 condition (input must be a rotation of sorted, forward or reversed) with some help.
  • Handles n = 1, n = 2 and already-sorted inputs.

Senior (L5)

  • Says on their own that only 2n arrangements are reachable, and models the state as (start, direction).
  • Writes the O(n) BFS cleanly and gets the flip transition right.
  • Notices that flip-rotate-flip rotates the other way, so the forward case is not just t. Tests that case.

Staff (L6+)

  • Names the dihedral-group structure and derives the closed form with a short proof that more flips never help.
  • Checks the closed form against min_ops_bfs or a brute-force BFS over real arrays before trusting it.
  • Discusses weighted costs, duplicates and prefix flips, and explains which of them break the state-space argument.

Sign in to comment, vote or remix.