Problem · Array

Min Operations to Sort All Packages

Learn this problem
EasyAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

In an Amazon distribution center, a large number of parcels arrive daily, each assigned a distinct identifier ranging from 1 to n. The warehouse supervisor is tasked with organizing these parcels, but not by their identifiers. Instead, they need to follow a specific order provided by the sortingSequence, which is a permutation of the integers from 1 to n, ensuring the most efficient handling.

Initially, no parcels have been organized (arrangedCount is 0). The supervisor checks the parcels from left to right. If a parcel's identifier matches the next one that needs to be organized (i.e., sortingSequence[i] == arrangedCount + 1), the supervisor arranges it and increments arrangedCount by one. If a parcel's identifier does not match the expected one in the permutation sequence, it is skipped.

Your task is to determine how many complete checks (operations) the supervisor must perform to organize all the parcels. Each operation involves checking all parcels from the first to the last.

Note: A sortingSequence is a valid permutation, meaning it is a sequence consisting of integers from 1 to n, each appearing exactly once. For example, [1, 3, 2] is a valid permutation, while [1, 2, 1] is not.

Function

packageSorting(sortingSequence: int[]) → int

Examples

Example 1

sortingSequence = [5, 3, 4, 1, 2]return = 3

The supervisor repeatedly checks the parcels from left to right, arranging each parcel whose identifier equals arrangedCount + 1.

  • Operation 1 arranges 1 and 2 (from positions of values 1 and 2).
  • Operation 2 arranges 3 and 4.
  • Operation 3 arranges 5, completing all parcels.

So, 3 operations are required to organize all the parcels.

Constraints

  • 1 <= n, where n is the length of sortingSequence
  • sortingSequence is a permutation of the integers from 1 to n, with each integer appearing exactly once
  • 1 <= sortingSequence[i] <= n

More Amazon problems

drafts saved locally
public int packageSorting(int[] sortingSequence) {
  // write your code here
}
sortingSequence[5, 3, 4, 1, 2]
expected3
checking account