Compute minimum passes to collect numbers
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Take-home Project
##### Question
You are given an array shelf of n distinct integers that is a permutation of 1…n. Starting with target = 1, you repeatedly scan shelf from left to right:
While scanning, if the current element equals target, you collect it and immediately increment target (target +=
1).
You never move left during a scan. When you reach the end of the array, if target ≤ n, you start a new full left-to-right pass and continue looking for the current target.
Return the minimum number of full passes required to collect all numbers 1…n.
Example: shelf = [3,1,5,4,2] → 3 passes (collect 1,2 in pass 1; 3,4 in pass 2; 5 in pass
3).
Design an O(n) algorithm and implement it.
Quick Answer: This question evaluates a candidate's ability to analyze array traversal patterns, permutation properties, and algorithmic efficiency, specifically reasoning about linear-time operations and state tracking across multiple left-to-right passes.
You are given an array shelf of n distinct integers that is a permutation of 1..n. Starting with target = 1, you repeatedly scan shelf from left to right in full passes. During a pass, whenever you encounter the current target, you collect it and immediately increment target by 1. You never move left within a pass. If after reaching the end target <= n, you start a new full pass. Return the minimum number of full passes needed to collect all numbers 1..n.
Constraints
- 1 <= n <= 200000
- shelf is a permutation of integers 1..n
- Time complexity should be O(n)
- Space complexity should be O(n)
Solution
from typing import List
def min_passes_to_collect(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(1, n):
if pos[x] > pos[x + 1]:
passes += 1
return passes
Explanation
Map each value v in 1..n to its index pos[v] in shelf. While scanning for 1..n in order, you can continue within the same pass as long as pos[i] < pos[i+1]. Whenever pos[i] > pos[i+1], you must start a new pass. Therefore, the number of passes equals 1 plus the count of such inversions between consecutive values.
Time complexity: O(n). Space complexity: O(n).
Hints
- Track the index (position) of each value 1..n in shelf.
- If position[i] < position[i+1], you can collect i and i+1 in the same pass; otherwise, you need a new pass.
- The answer equals 1 plus the number of i in [1..n-1] where position[i] > position[i+1].