3638. Maximum Balanced Shipments

Medium

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To maximize the number of balanced shipments, we want to end each shipment as soon as we can form a balanced one. For a shipment to be balanced, the last parcel must be strictly less than the maximum value seen so far in the current segment. As we go through the array, we keep track of the running maximum. Every time the current parcel is less than this maximum, we can close a shipment with this parcel as the end, count it, and start looking for the next shipment from the next parcel. This greedy approach works because making shipments as early as possible allows us to use more parcels in non-overlapping shipments, maximizing the total count.

Solution Approach

The solution uses a greedy strategy with a single pass through the array. We keep two variables: mx, which tracks the maximum weight seen so far in the current potential shipment, and ans, which counts the number of balanced shipments we have formed.

As we iterate through each parcel weight x in the array:
- Update mx as the maximum between the current mx and x.
- If x < mx, this means x can be the end of a balanced shipment: the current shipment's last parcel is strictly less than the maximum in the segment.
  - Increment ans by 1 to count this shipment.
  - Reset mx to 0 to start tracking a new possible shipment from the next parcel.
- If not, continue and update mx with the next element.
After traversing the array, return ans as the answer.

This logic ensures each shipment is as short as possible (ending as soon as it's balanced), maximizing the overall count. The approach runs in O(n) time and uses constant space, since only two variables are maintained throughout the traversal.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the array weight = [4, 2, 6, 5, 3].

Let's walk through the greedy algorithm step by step:

Start: mx = 0, ans = 0.
First parcel (4):
- Update mx = max(0, 4) = 4.
- 4 is not less than 4, so no shipment ends here.
Second parcel (2):
- Update mx = max(4, 2) = 4.
- 2 < 4 ⇒ This can end a balanced shipment.
- Increment ans = 1, reset mx = 0.
Third parcel (6):
- Update mx = max(0, 6) = 6.
- 6 is not less than 6, continue.
Fourth parcel (5):
- Update mx = max(6, 5) = 6.
- 5 < 6 ⇒ This can end a balanced shipment.
- Increment ans = 2, reset mx = 0.
Fifth parcel (3):
- Update mx = max(0, 3) = 3.
- 3 is not less than 3, so no shipment ends here.

Result: You can create at most 2 balanced shipments:

Shipment 1: [4, 2] (ends at 2, since 2 < 4)
Shipment 2: [6, 5] (ends at 5, since 5 < 6)

The last parcel (3) remains unshipped, as it cannot form a balanced shipment.

This stepwise approach shows how the greedy logic maximizes the number of balanced shipments by closing a shipment at the first possible opportunity each time.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxBalancedShipments(self, weight: List[int]) -> int:
5        # ans: Counts the number of balanced shipments (splits)
6        # max_weight: Tracks the maximum value seen in the current segment
7        ans = 0
8        max_weight = 0
9
10        # Iterate through the weights list
11        for w in weight:
12            # Update the maximum weight seen so far
13            max_weight = max(max_weight, w)
14
15            # If current weight is less than the maximum in this segment,
16            # this indicates a balanced shipment point
17            if w < max_weight:
18                ans += 1   # Increment the shipment count
19                max_weight = 0  # Reset max for the next segment
20
21        return ans
22

1class Solution {
2    public int maxBalancedShipments(int[] weight) {
3        int answer = 0; // Counts the number of balanced shipments
4        int maxWeightSoFar = 0; // Tracks the maximum weight seen in current segment
5
6        // Iterate through each shipment weight
7        for (int w : weight) {
8            // Update the maximum weight seen so far
9            maxWeightSoFar = Math.max(maxWeightSoFar, w);
10
11            // If current weight is less than the max in this segment,
12            // we've found an unbalanced spot to split the shipment
13            if (w < maxWeightSoFar) {
14                answer++;         // Increment balanced shipment count
15                maxWeightSoFar = 0; // Reset max for the next segment
16            }
17        }
18        return answer;
19    }
20}
21

1class Solution {
2public:
3    // Calculates the maximum number of balanced shipments
4    int maxBalancedShipments(vector<int>& weight) {
5        int ans = 0;   // Stores the count of shipments
6        int maxWeight = 0; // Tracks the maximum weight seen so far
7
8        // Iterate over each weight
9        for (int w : weight) {
10            maxWeight = std::max(maxWeight, w); // Update the max weight
11
12            // If current weight is less than the max seen so far,
13            // it indicates a point to split (form a new shipment)
14            if (w < maxWeight) {
15                ++ans;           // Increment the count of shipments
16                maxWeight = 0;   // Reset maxWeight for the next segment
17            }
18        }
19
20        return ans; // Return the result
21    }
22};
23

1// Returns the maximum number of balanced shipments possible given weights
2function maxBalancedShipments(weight: number[]): number {
3    // ans: counts the number of balanced shipments
4    // maxWeight: holds the highest weight seen so far in the current segment
5    let ans = 0;
6    let maxWeight = 0;
7    // Iterate through each weight in the array
8    for (const currentWeight of weight) {
9        // Update the maximum weight in the current segment
10        maxWeight = Math.max(maxWeight, currentWeight);
11        // If currentWeight is smaller than the maximum seen so far,
12        // it means the current segment cannot be extended further for balancing
13        if (currentWeight < maxWeight) {
14            ans++;           // Increment the count of balanced shipments
15            maxWeight = 0;   // Reset maxWeight for the next segment
16        }
17    }
18    return ans;
19}
20

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the weight array, because it iterates through the array once.

The space complexity is O(1), as it uses only a fixed number of variables (ans, mx, and the loop variable x) regardless of the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know