How should I practice Maximum Number of Balanced Shipments?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Amazon online assessment problems in FastPrep.

Is Maximum Number of Balanced Shipments associated with Amazon?

FastPrep tags this as a Amazon coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Greedy

Maximum Number of Balanced Shipments

Learn this problem

● MediumAmazonNEW GRADOA

See Amazon hiring insights

Problem statement

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.

Function

findMaximumBalancedShipments(parcelWeights: int[]) → int

Examples

Example 1

parcelWeights = [1, 2, 3, 2, 6, 3]return = 2

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.

Example 2

parcelWeights = [8, 5, 4, 7, 2]return = 2

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.

Example 3

parcelWeights = [4, 3, 6, 5, 3, 4, 7, 1]return = 3

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

1 <= n <= 10^5
1 <= parcelWeights[i] <= 10^9