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