Problem 264292 · hard · Phase 02 Linear Data Structures

Tidy Garage With One Empty Spot

arrays · permutations · cycles · counting

A narrow garage has n spots numbered 0 to n - 1. Spot i holds car lot[i], where the value 0 marks the single empty spot and cars are numbered 1 to n - 1. The garage is tidy when car c stands in spot c for every car, which leaves spot 0 empty.

Cars can only be parked in the empty spot: in one move, you drive any one car into the empty spot, and the spot it left becomes the new empty spot.

Return the minimum number of moves that makes the garage tidy.

Examples

Input:  lot = [0, 2, 1]
Output: 3
Explanation: car 2 -> spot 0, car 1 -> spot 1, car 2 -> spot 2.

Input:  lot = [2, 0, 1]
Output: 2
Explanation: car 1 -> spot 1, then car 2 -> spot 2.

Input:  lot = [3, 0, 1, 2, 5, 4]
Output: 6

Constraints

  • 1 <= n <= 10**5
  • lot holds each of 0 .. n - 1 exactly once.
  • Target: O(n) time. Searching the list for a car before every move is far too slow for the largest tests.

Goals

  • Model a rearrangement as cycles of 'who belongs where'
  • Price the cycle that holds the empty spot differently from the others
  • Count moves without simulating them
Starting Python…