FastPrepFastPrep
Problem Brief

Maximum Number of Balanced Shipments

NEW GRADOA
See Amazon online assessment and hiring insights

Amazon operates numerous distribution hubs for delivering its products. At one such hub, parcels are organized in a row where the ith parcel has a specific mass denoted by parcelWeights[i].

A shipment consists of a continuous subsequence of parcels from this arrangement. For example, given parcels with weights [3, 6, 3], possible shipments include [3], [6], [3], [3, 6], [6, 3], and [3, 6, 3]. However, [3, 3] is not considered a valid shipment as it is not contiguous.

A shipment is regarded as balanced if the mass of the last parcel in the shipment is not the greatest among all the parcels in that shipment. For instance, for a shipment with weights [3, 9, 4, 7], it is balanced because the last parcel's weight is 7, while the heaviest parcel weighs 9. Conversely, the shipment [4, 7, 2, 7] is not balanced.

Given a series of parcel weights, determine the highest number of balanced shipments that can be created such that each parcel is included in exactly one shipment, all shipments contain only a contiguous sequence of parcels, and every shipment remains balanced. Return 0 if no balanced shipments are possible.

1Example 1

Input
parcelWeights = [1, 2, 3, 2, 6, 3]
Output
2
Explanation
Example 1 illustration
Theparcels can be divided into two shipments: [1, 2, 3, 2] and [6, 3]. Both are balanced. It can be confirmed that this is the maximum number of shipments that can be formed, resulting in the answer 2.

2Example 2

Input
parcelWeights = [8, 5, 4, 7, 2]
Output
2
Explanation
Possible balanced shipments include [8, 5] and [4, 7, 2], or [8, 5, 4] and [7, 2]. In both cases, the maximum number of shipments is 2.

3Example 3

Input
parcelWeights = [4, 3, 6, 5, 3, 4, 7, 1]
Output
3
Explanation
Some valid ways to form balanced shipments are: [4, 3, 6, 5] and [3, 4, 7, 1], or [4, 3], [6, 5], and [3, 4, 7, 1], or [4, 3, 6, 5, 3] and [4, 7, 1]. It is not possible to form more than 3 balanced shipments, so the final answer is 3.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 10^5
  • 1 <= parcelWeights[i] <= 10^9
    • public int maxNumberOfBalancedShipments(int[] parcelWeights) {
  // write your code here
}
    Input

    parcelWeights

    [1, 2, 3, 2, 6, 3]

    Output

    2

    Sign in to submit your solution.