Compute minimum passes to collect numbers
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
##### 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.
Overview: 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)
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].