Compute minimum passes over permutation

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.

Minimum Passes Over a Permutation

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)

Examples

Example 1

Input: shelf = [2,1,3,4]
Output: 2

Explanation: Pass 1: find 1; need another pass to find 2,3,4. Pass 2: find 2, then 3, then 4. Total passes = 2.

Example 2

Input: shelf = [1,2,3,4]
Output: 1

Explanation: All numbers are found in order during the first scan. Total passes = 1.

Hints

1. Record the index (position) of each value in shelf.
2. Consider the sequence of positions pos[1], pos[2], ..., pos[n].
3. A new pass is needed whenever pos[i] < pos[i-1]. The answer is 1 plus the count of such breaks.

Approach

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)