You are given an integer array weight of length n, representing the weights of n parcels arranged in a straight line. A shipment is defined as a contiguous subarray of parcels. A shipment is considered balanced if the weight of the last parcel is strictly less than the maximum weight among all parcels in that shipment.
Select a set of non-overlapping, contiguous, balanced shipments such that each parcel appears in at most one shipment (parcels may remain unshipped).
Return the maximum possible number of balanced shipments that can be formed.
Example 1:
Input: weight = [2,5,1,4,3]
Output: 2
Explanation:
We can form the maximum of two balanced shipments as follows:
[2, 5, 1]
[4, 3]
It is impossible to partition the parcels to achieve more than two balanced shipments, so the answer is 2.
Example 2:
Input: weight = [4,4]
Output: 0
Explanation:
No balanced shipment can be formed in this case:
[4, 4] has maximum weight 4 and the last parcel's weight is also 4, which is not strictly less. Thus, it's not balanced.[4] have the last parcel weight equal to the maximum parcel weight, thus not balanced.As there is no way to form even one balanced shipment, the answer is 0.
Constraints:
2 <= n <= 1051 <= weight[i] <= 109Problem Overview: You are given an array of package weights. The goal is to split the sequence into the maximum number of shipments such that each shipment is balanced. A shipment becomes balanced once the last package in that segment is strictly smaller than the maximum weight seen earlier in the same shipment.
Approach 1: Greedy with Running Maximum (O(n) time, O(1) space)
Traverse the array while tracking the maximum weight seen in the current shipment using a variable like currentMax. When the current package weight becomes smaller than currentMax, the shipment is balanced because a heavier package already exists earlier in that segment. At that point, increment the shipment count and reset the state to start a new shipment. This greedy strategy works because closing a shipment as soon as it becomes valid leaves the most remaining elements available for future shipments.
Approach 2: Monotonic Stack Tracking Maximums (O(n) time, O(n) space)
A monotonic stack can also track decreasing weights while scanning the array. Push elements while maintaining a decreasing structure so the top represents the largest candidate within the current shipment. When a new element is smaller than the maximum stored in the stack, the shipment satisfies the balance condition. At that point you finalize the shipment, clear the stack, and begin a new segment. This approach explicitly models the decreasing structure and is useful when the condition involves comparing with previous greater elements.
Approach 3: Dynamic Programming Interpretation (O(n) time, O(n) space)
You can frame the problem using dynamic programming where dp[i] represents the maximum number of balanced shipments using the first i packages. While iterating, track the maximum value within the current segment and update dp whenever the balance condition is satisfied. Although correct, this formulation adds unnecessary state because the greedy decision already guarantees optimal segmentation.
Recommended for interviews: The greedy single-pass approach is what interviewers typically expect. It shows you recognized the key invariant: once a shipment becomes balanced, closing it immediately maximizes the number of future shipments. Mentioning how the idea relates to greedy algorithms and optionally discussing the monotonic stack variant demonstrates deeper understanding of sequence processing patterns.
We maintain the maximum value mx of the currently traversed array, and iterate through each element x in the array. If x < mx, it means the current element can serve as the last parcel of a balanced shipment, so we increment the answer by one and reset mx to 0. Otherwise, we update mx to the value of the current element x.
After the traversal, we return the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1), using only constant extra space.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Running Maximum | O(n) | O(1) | Best general solution. Single pass and minimal memory. |
| Monotonic Stack | O(n) | O(n) | Useful when explicitly tracking previous greater elements. |
| Dynamic Programming | O(n) | O(n) | Conceptual understanding of segment optimization problems. |
Leetcode 3638 | Leetcode 3639 | Maximum Balanced Shipments | Minimum Time to Activate String • CodeWithMeGuys • 304 views views
Watch 7 more video solutions →Practice Maximum Balanced Shipments with our built-in code editor and test cases.
Practice on FleetCode