Compute minimum passes over permutation
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### Question
You are given an array shelf representing a permutation of the integers 1..n. Starting with target = 1, you repeatedly scan the array left-to-right. During a scan, whenever you encounter the current target value you immediately update target ← target + 1 and continue scanning to the right in the same pass. When you reach the end of the array, if target ≤ n you start a new full left-to-right pass, resuming the search for that target. Compute the minimum number of full passes required to find all numbers 1..n.
Quick Answer: This question evaluates algorithmic problem-solving skills focused on array traversal and permutation analysis, testing understanding of sequential scanning behavior and state progression within the Coding & Algorithms domain.
You are given a list shelf representing a permutation of the integers 1..n. Starting with target = 1, repeatedly scan shelf from left to right in passes. In a pass, whenever you encounter the current target value, increment target by 1 and continue scanning to the right within the same pass. When you reach the end of the list, if target ≤ n, start another pass from the beginning. Return the minimum number of passes that must be initiated until all numbers 1..n are found (i.e., until target becomes n+1).
Constraints
- 1 ≤ n ≤ 200000
- shelf is a permutation of [1, 2, ..., n]
- Expected time complexity: O(n)
- Expected auxiliary space: O(n)
Solution
from typing import List
def min_passes(shelf: List[int]) -> int:
n = len(shelf)
if n == 0:
return 0
pos = [0] * (n + 1)
for i, v in enumerate(shelf):
pos[v] = i
passes = 1
for x in range(2, n + 1):
if pos[x] < pos[x - 1]:
passes += 1
return passes
Explanation
Map each value v to its index pos[v]. During a single left-to-right pass, you can collect values whose positions are in nondecreasing order with respect to their value order 1..n. Each time the position decreases from pos[i-1] to pos[i], a new pass is required. Therefore, the answer equals 1 plus the number of i in [2..n] with pos[i] < pos[i-1].
Time complexity: O(n). Space complexity: O(n).
Hints
- Record the index (position) of each value in shelf.
- Consider the sequence of positions pos[1], pos[2], ..., pos[n].
- A new pass is needed whenever pos[i] < pos[i-1]. The answer is 1 plus the count of such breaks.