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 in that shipment is strictly less than the maximum weight among all parcels in that shipment.

Your task is to select a set of non-overlapping, contiguous, balanced shipments such that each parcel appears in at most one shipment (some parcels may remain unshipped).

Return the maximum possible number of balanced shipments that can be formed.

For example, if we have parcels with weights [3, 5, 2, 7, 4]:

• The subarray [3, 5, 2] is a balanced shipment because the last parcel (2) is less than the maximum weight (5)
• The subarray [7, 4] is a balanced shipment because the last parcel (4) is less than the maximum weight (7)
• These two shipments don't overlap, giving us 2 balanced shipments total

The greedy approach works by traversing the array and keeping track of the maximum weight seen so far. Whenever we find a parcel whose weight is less than the current maximum, we can end a balanced shipment there (using that parcel as the last one), increment our count, and start looking for the next shipment.

Intuition

The key insight is that we want to maximize the number of balanced shipments, which means we should try to create shipments as soon as possible rather than making them longer.

Think about it this way: when we traverse the array and keep track of the maximum weight seen so far, whenever we encounter a parcel that is lighter than this maximum, we have an opportunity to form a balanced shipment. Why should we take this opportunity immediately?

Consider what happens if we don't end the shipment here and continue:

• We might encounter an even heavier parcel later, which would update our maximum
• The next opportunity to end a shipment would require finding a parcel lighter than this new, potentially higher maximum
• This makes it harder to form balanced shipments

By greedily ending a shipment as soon as we find a valid ending parcel (one that's lighter than the current maximum), we:

1. Secure one balanced shipment immediately
2. Reset our tracking, allowing us to start fresh for the next potential shipment
3. Avoid the risk of making it harder to form future shipments by accumulating higher maximum values

For example, with weights [3, 5, 2, 7, 4]:

• We see 3, then 5 (max becomes 5)
• We see 2, which is less than 5 - we can form a balanced shipment [3, 5, 2]
• If we had continued without ending here, we'd see 7 next, making our max 7, and then 4 would still give us one shipment but we'd have missed the opportunity to form two

This greedy strategy of "take the first valid opportunity" ensures we maximize the total number of balanced shipments we can form.

Learn more about Stack, Greedy, Dynamic Programming and Monotonic Stack patterns.

Solution Approach

The implementation uses a greedy algorithm with a simple linear scan through the array. Here's how it works:

We maintain two variables:

• ans: counts the number of balanced shipments formed
• mx: tracks the maximum weight in the current potential shipment

The algorithm processes each parcel weight x in the array sequentially:

1. Update the maximum: For each element x, we update mx = max(mx, x) to maintain the maximum weight seen in the current segment.

2. Check for balanced shipment opportunity: If x < mx, this means the current parcel can serve as the last parcel of a balanced shipment (since it's strictly less than the maximum weight in the segment).

3. Form a shipment and reset: When we find such an opportunity:

   • Increment ans by 1 (we've formed one balanced shipment)
   • Reset mx to 0 to start tracking a new potential shipment

Here's the step-by-step execution with an example weight = [3, 5, 2, 7, 4]:

• x = 3: mx = max(0, 3) = 3, not less than mx, continue
• x = 5: mx = max(3, 5) = 5, not less than mx, continue
• x = 2: mx = 5, and 2 < 5, so we form a shipment, ans = 1, reset mx = 0
• x = 7: mx = max(0, 7) = 7, not less than mx, continue
• x = 4: mx = 7, and 4 < 7, so we form a shipment, ans = 2, reset mx = 0

The time complexity is O(n) since we make a single pass through the array, and the space complexity is O(1) as we only use two variables regardless of input size.

This greedy approach is optimal because forming a shipment as soon as possible never prevents us from forming future shipments - it only creates more opportunities by resetting our tracking.

Example Walkthrough

Let's walk through the solution with a simple example: weight = [4, 6, 3, 8, 5, 2]

We'll track two variables:

• ans = 0 (number of balanced shipments formed)
• mx = 0 (maximum weight in current segment)

Step 1: Process weight 4

• Update mx = max(0, 4) = 4
• Is 4 < 4? No, so continue
• Current segment: [4]

Step 2: Process weight 6

• Update mx = max(4, 6) = 6
• Is 6 < 6? No, so continue
• Current segment: [4, 6]

Step 3: Process weight 3

• mx is still 6
• Is 3 < 6? Yes! We can form a balanced shipment
• The shipment [4, 6, 3] is balanced (last element 3 < max element 6)
• Increment ans = 1 and reset mx = 0

Step 4: Process weight 8

• Update mx = max(0, 8) = 8
• Is 8 < 8? No, so continue
• Current segment: [8]

Step 5: Process weight 5

• mx is still 8
• Is 5 < 8? Yes! We can form another balanced shipment
• The shipment [8, 5] is balanced (last element 5 < max element 8)
• Increment ans = 2 and reset mx = 0

Step 6: Process weight 2

• Update mx = max(0, 2) = 2
• Is 2 < 2? No, so continue
• We've reached the end

Result: We formed 2 balanced shipments: [4, 6, 3] and [8, 5]. The parcel with weight 2 remains unshipped, which is allowed by the problem.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array weight. The algorithm iterates through the array exactly once with a single for loop, performing constant-time operations (comparisons, assignments, and max function) at each iteration.

The space complexity is O(1), using only constant extra space. The algorithm only uses a fixed number of variables (ans, mx, and x) regardless of the input size, with no additional data structures that grow with the input.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Greedy Reset Logic

A common mistake is thinking that resetting current_max to 0 after forming a shipment might miss optimal solutions. Developers might worry: "What if I could form a longer balanced shipment by not greedily taking the first opportunity?"

Why this concern is unfounded: The greedy approach is actually optimal here. Once we find a valid ending point for a balanced shipment (where current_weight < current_max), extending this shipment further can never increase our total count - at best, we get the same single shipment but longer. By taking the shipment immediately, we maximize opportunities for future shipments.

Pitfall 2: Incorrect Initialization of Maximum

Some might initialize current_max to the first element of the array or to float('-inf'), thinking they need a proper starting comparison value.

Issue with wrong initialization:

• If initialized to weight[0], you'd need special handling for the first element
• If initialized to float('-inf'), every single-element segment would incorrectly be considered balanced

Solution: Initialize current_max to 0. This works because:

• All weights are positive integers (based on the problem context)
• The first element will properly set current_max on the first iteration
• It naturally handles empty arrays

Pitfall 3: Off-by-One Errors in Shipment Formation

Developers might accidentally form a shipment that includes the current element as part of the next shipment rather than ending the current shipment with it.

Incorrect approach:

if current_weight < current_max:
    balanced_count += 1
    current_max = current_weight  # Wrong! This includes current element in next shipment

Correct approach:

if current_weight < current_max:
    balanced_count += 1
    current_max = 0  # Correct! Start fresh for next shipment

The current element that satisfies the condition is the last element of the current shipment, not the first element of the next one.