LeetCode 3638 - Maximum Balanced Shipments

LeetCode Problem 3638

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Stack, Greedy, Monotonic Stack

Solution

Problem Understanding

We are given an array weight representing parcels arranged in a line. We must partition some prefix-suffix segments of this array into a collection of non-overlapping contiguous subarrays called shipments. Each parcel can belong to at most one shipment, and it is also allowed to leave some parcels unused.

A shipment is considered valid, or balanced, if within that subarray the last element is strictly smaller than the maximum element anywhere in the same subarray. In other words, if we denote a shipment [l, r], then it is valid if:

max(weight[l..r]) > weight[r]

The task is to choose as many such valid subarrays as possible, under the constraint that they do not overlap.

The output is the maximum number of balanced shipments that can be formed.

The constraints indicate that n can be up to 10^5, so an O(n^2) or worse solution will not scale. The values in weight can be large, but only relative comparisons matter.

Important edge cases include arrays where all values are equal, where no valid segment can exist, and arrays where valid segments exist but are sparsely distributed, requiring careful greedy partitioning.

Approaches

Brute Force Approach

A brute force solution would try every possible way to partition the array into contiguous segments and then check each segment for validity. For each partition, we would compute the maximum in each segment and compare it to the last element. This leads to an exponential number of partitions, and even if we restrict ourselves to checking all subarrays, we still end up with an O(n^2) or O(n^3) solution depending on implementation.

This approach is correct in principle because it explores all possible segmentations, but it is far too slow for n = 10^5.

Key Insight

The key observation is that a segment [l, r] is valid if and only if there exists at least one element in [l, r-1] that is strictly greater than weight[r]. This means the validity of ending a segment at r depends only on whether we have seen a larger element earlier in the current segment.

This leads to a greedy strategy: we scan left to right, maintaining the maximum value in the current open segment. As soon as we reach an index r where the current maximum is greater than weight[r], we know we can safely end a valid segment at r. To maximize the number of segments, we should end it immediately at the earliest possible valid point.

This greedy cut works because extending a valid segment further can only delay future segments and cannot improve the number of valid partitions.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2) to O(2^n)	O(1) to O(n)	Tries all partitions or subarrays
Optimal Greedy	O(n)	O(1)	Single pass with running maximum

Algorithm Walkthrough

The optimal algorithm proceeds in a single pass while maintaining the current segment’s maximum value.

1. We initialize a counter ans = 0 to store the number of balanced shipments and a variable current_max to track the maximum value in the current open segment.
2. We iterate through the array from left to right, treating each index as a potential endpoint of the current segment.
3. At each index i, we update current_max = max(current_max, weight[i]) because we are extending the current segment to include the new element.
4. We check whether the current segment can be closed at i. This is possible if current_max > weight[i], meaning there exists at least one earlier element in the segment that is strictly greater than the last element.
5. If the condition holds, we increment the answer by one because we have formed a valid balanced shipment ending at i.
6. We then reset the segment by setting current_max = 0 (or reinitializing it for the next segment), and continue scanning from the next index.

Why it works

The correctness comes from a greedy cut property: among all valid segment endings, choosing the earliest valid endpoint maximizes the number of disjoint segments. Once a segment becomes valid, extending it further cannot increase the number of segments overall, and may only reduce future opportunities. Thus, every time we can legally close a segment, we do so immediately. We are given an array weight, where weight[i] is the weight of the i-th parcel in a line.

A shipment is any contiguous subarray. A shipment is balanced if the weight of its last parcel is strictly smaller than the maximum weight that appears anywhere inside that shipment.

For a shipment weight[l..r], the condition is

$$weight[r] < \max(weight[l], weight[l+1], \dots, weight[r]).$$

We may select multiple shipments, but they must be non-overlapping. Every parcel can belong to at most one selected shipment. Parcels that do not belong to any shipment may simply be ignored.

The goal is to maximize the number of balanced shipments.

The constraints are important:

• 2 <= n <= 10^5
• 1 <= weight[i] <= 10^9

Since n can be as large as 100000, any solution that examines all subarrays is far too slow. We need a linear or near-linear algorithm.

Several edge cases are worth noting:

• Arrays with all equal values, such as [4,4], cannot form a balanced shipment because the last element is never strictly smaller than the maximum.
• A single parcel is never balanced because its last element equals the maximum.
• A shipment becomes balanced as soon as we encounter an element that is strictly smaller than a previous maximum in the same shipment.
• Since parcels may remain unused, we are not required to partition the entire array.

Approaches

Brute Force

A natural brute-force idea is dynamic programming over intervals.

For every starting position i, we could try every ending position j, determine whether weight[i..j] is balanced, and then compute the best answer obtainable after position j.

Checking all subarrays requires $O(n^2)$ intervals. Even if balance checks are optimized with prefix maxima, the number of intervals remains quadratic.

Since $n = 10^5$, an $O(n^2)$ algorithm is completely infeasible.

Key Insight

Consider building shipments from left to right.

Suppose we start a candidate shipment immediately after the previous shipment ended. Let

$$M = \max(\text{elements seen in the current candidate shipment}).$$

The first time we encounter an element x such that

$$x < M,$$

the current segment is already balanced. At that moment we have a choice:

• End the shipment now.
• Extend it further.

Ending immediately is always at least as good.

Why? Because the shipment is already valid. Extending it only consumes additional parcels that might otherwise be used to form future shipments. Therefore, among all balanced shipments beginning at the current start position, the earliest possible ending position is always optimal.

This yields a greedy strategy:

• Maintain the maximum value in the current unfinished segment.
• Scan from left to right.
• Whenever the current value is strictly less than that maximum, immediately close a shipment.
• Start a new candidate shipment after that position.

Each shipment produced in this way is the shortest possible balanced shipment starting from its start position, which leaves the maximum number of parcels available for future shipments.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Examines many possible intervals
Optimal Greedy	O(n)	O(1)	Close each shipment at the earliest valid position

Algorithm Walkthrough

1. Initialize count = 0.
2. Begin a new candidate shipment at the first unprocessed parcel.
3. Maintain current_max, the maximum weight seen in the current candidate shipment.
4. Scan the array from left to right.
5. For each parcel:

• Update current_max.
• If the current parcel is strictly smaller than current_max, then the current segment is balanced.

6. As soon as a balanced segment is found:

• Increment the answer.
• Reset the state to begin a completely new candidate shipment after the current position.

7. Continue until the end of the array.

The reset is crucial. Once a balanced shipment is completed, extending it cannot increase the number of shipments. Ending it immediately preserves the largest possible suffix for future shipments.

Why it works

The greedy choice is to end a shipment at the earliest position where it becomes balanced.

Consider any optimal solution. Let the first shipment begin at the same start position as the greedy shipment. If that optimal shipment ends later than the greedy shipment, replacing it by the greedy shipment still yields a valid balanced shipment and leaves more parcels available afterward. Therefore the replacement cannot reduce the number of future shipments.

Thus there exists an optimal solution whose first shipment is exactly the greedy shipment. Applying the same argument recursively to the remaining suffix proves that every greedy choice is optimal. Therefore the algorithm produces the maximum possible number of balanced shipments.

Python Solution

from typing import List

class Solution:
    def maxBalancedShipments(self, weight: List[int]) -> int:
        ans = 0
        current_max = 0
        
        for w in weight:
            current_max = max(current_max, w)
            
            if current_max > w:
                ans += 1
                current_max = 0
        
        return ans

The implementation maintains a running maximum for the current segment. As we iterate through each parcel, we update this maximum. If the current element is strictly smaller than the maximum seen so far, it means we can safely end a balanced shipment at this index. We then increment the result and reset the tracking variable to start a new segment. shipments = 0 current_max = 0 active = False

    for w in weight:
        if not active:
            current_max = w
            active = True
        else:
            if w < current_max:
                shipments += 1
                active = False
            else:
                current_max = max(current_max, w)

    return shipments

The implementation maintains the state of the current unfinished shipment.

When `active` is `False`, we are starting a new candidate shipment and initialize its maximum.

When `active` is `True`, we check whether the current weight is strictly smaller than the maximum already seen. If it is, the shipment is balanced and we immediately close it. The counter is incremented and the state is reset so that the next parcel begins a new candidate shipment.

If the current weight is not smaller than the maximum, the shipment is not yet balanced, so we simply update the running maximum and continue.

## Go Solution

```go
package main

func maxBalancedShipments(weight []int) int {
	ans := 0
	currentMax := 0

	for _, w := range weight {
		if w > currentMax {
			currentMax = w
		}

		if currentMax > w {
			ans++
			currentMax = 0
		}
	}

	return ans
}

The Go implementation mirrors the Python logic closely. We use a single integer currentMax to track the maximum in the current segment. Since Go does not have built-in max for integers in older versions, we use a simple comparison. Resetting currentMax to zero cleanly starts a new segment.

Worked Examples

Example 1: weight = [2, 5, 1, 4, 3]

We track current_max and decisions step by step.

Index	Weight	Current Max	Condition max > w	Action	Shipments
0	2	2	No	continue	0
1	5	5	No	continue	0
2	1	5	Yes	cut here, reset	1
3	4	4	No	continue	1
4	3	4	Yes	cut here, reset	2

Final answer is 2.

Example 2: weight = [4, 4]

Index	Weight	Current Max	Condition	Action	Shipments
0	4	4	No	continue	0
1	4	4	No	continue	0

No valid segment can be formed, so the result is 0. func maxBalancedShipments(weight []int) int { shipments := 0 currentMax := 0 active := false

for _, w := range weight {
	if !active {
		currentMax = w
		active = true
	} else {
		if w < currentMax {
			shipments++
			active = false
		} else if w > currentMax {
			currentMax = w
		}
	}
}

return shipments

}

The Go implementation follows exactly the same logic as the Python version.

The only notable difference is that Go uses explicit variables instead of Python's dynamic typing. Since all weights are at most `10^9`, standard Go `int` arithmetic is completely safe on LeetCode platforms.

## Worked Examples

### Example 1

Input:

weight = [2,5,1,4,3]

| Index | Weight | Current Max | Action | Shipments |
| --- | --- | --- | --- | --- |
| 0 | 2 | 2 | Start candidate shipment | 0 |
| 1 | 5 | 5 | Update maximum | 0 |
| 2 | 1 | 5 | 1 < 5, close shipment | 1 |
| 3 | 4 | 4 | Start new candidate shipment | 1 |
| 4 | 3 | 4 | 3 < 4, close shipment | 2 |

The two shipments are:

[2,5,1] [4,3]

Answer:

2

### Example 2

Input:

weight = [4,4]

| Index | Weight | Current Max | Action | Shipments |
| --- | --- | --- | --- | --- |
| 0 | 4 | 4 | Start candidate shipment | 0 |
| 1 | 4 | 4 | Not smaller than maximum | 0 |

No balanced shipment is ever formed.

Answer:

0

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Single pass through the array with constant-time updates per element |
| Space | O(1) | Only a few integer variables are used regardless of input size |

The algorithm is optimal because every element is processed exactly once, and no auxiliary data structures scale with input size.

## Test Cases

assert Solution().maxBalancedShipments([2, 5, 1, 4, 3]) == 2 # sample case with multiple valid cuts assert Solution().maxBalancedShipments([4, 4]) == 0 # no valid shipment possible assert Solution().maxBalancedShipments([1, 2, 3, 4]) == 0 # strictly increasing, never valid assert Solution().maxBalancedShipments([3, 1, 3, 1, 3, 1]) == 3 # alternating pattern allows many cuts assert Solution().maxBalancedShipments([5, 1, 2, 6, 1]) == 2 # mixed structure assert Solution().maxBalancedShipments([1, 1, 1, 2]) == 0 # equal values prevent validity assert Solution().maxBalancedShipments([2, 1]) == 1 # single valid segment at end

| Test | Why |
| --- | --- |
| `[2,5,1,4,3]` | standard case with optimal greedy cuts |
| `[4,4]` | all equal, no valid segment exists |
| `[1,2,3,4]` | monotonic increase prevents any valid ending |
| `[3,1,3,1,3,1]` | alternating highs enable repeated valid cuts |
| `[5,1,2,6,1]` | mixed peaks test correctness of greedy reset |
| `[1,1,1,2]` | repeated values test strict inequality |
| `[2,1]` | minimal valid segment case |

## Edge Cases

One important edge case is when all elements are equal. In this scenario, no segment can ever be balanced because the maximum element is always equal to the last element, violating the strict inequality requirement. The algorithm handles this naturally because `current_max > w` never becomes true.

Another edge case is a strictly increasing array. Here, every segment’s last element is always the maximum of that segment, so no valid shipment can ever be formed. The greedy scan simply never triggers a cut, resulting in zero.

A final edge case involves small arrays of size two. If the first element is greater than the second, a single valid shipment can be formed. Otherwise, no shipment is possible. The algorithm correctly evaluates this because it immediately compares the current maximum against the last element at each step and decides whether a valid boundary exists.
| Time | O(n) | Single left-to-right scan |
| Space | O(1) | Only a few variables are stored |

The algorithm examines each parcel exactly once. Every iteration performs only constant-time work, so the running time is linear in the length of the array. No auxiliary data structures proportional to `n` are used.

## Test Cases

```python
from typing import List

class Solution:
    def maxBalancedShipments(self, weight: List[int]) -> int:
        shipments = 0
        current_max = 0
        active = False

        for w in weight:
            if not active:
                current_max = w
                active = True
            else:
                if w < current_max:
                    shipments += 1
                    active = False
                else:
                    current_max = max(current_max, w)

        return shipments

s = Solution()

assert s.maxBalancedShipments([2, 5, 1, 4, 3]) == 2      # example 1
assert s.maxBalancedShipments([4, 4]) == 0               # example 2

assert s.maxBalancedShipments([5, 1]) == 1               # smallest balanced shipment
assert s.maxBalancedShipments([1, 2]) == 0               # increasing pair
assert s.maxBalancedShipments([3, 1, 2, 1]) == 2         # two short shipments
assert s.maxBalancedShipments([5, 1, 1]) == 1            # greedy closes early
assert s.maxBalancedShipments([1, 1, 1, 1]) == 0         # all equal
assert s.maxBalancedShipments([5, 4, 3, 2, 1]) == 2      # multiple disjoint shipments
assert s.maxBalancedShipments([1, 3, 2, 4, 3, 5, 4]) == 3  # repeated pattern
assert s.maxBalancedShipments([10, 1, 10, 1, 10, 1]) == 3  # maximum packing

Test Summary

Test	Why
[2,5,1,4,3]	Official example
[4,4]	Official example with no solution
[5,1]	Smallest possible balanced shipment
[1,2]	Strictly increasing array
[3,1,2,1]	Multiple independent shipments
[5,1,1]	Verifies early greedy termination
[1,1,1,1]	Equal values everywhere
[5,4,3,2,1]	Decreasing sequence
[1,3,2,4,3,5,4]	Repeated balanced patterns
[10,1,10,1,10,1]	Stress test for maximum shipment count

Edge Cases

A particularly important edge case is an array where all values are equal, such as [4,4,4,4]. In every possible shipment, the final element equals the maximum element of that shipment. Since the condition requires a strict inequality, no shipment is balanced. The implementation correctly returns 0 because it never encounters an element strictly smaller than the current maximum.

Another important case is a strictly increasing array such as [1,2,3,4,5]. Every new element becomes the current maximum, so the balance condition is never satisfied. The scan reaches the end without closing any shipment, producing the correct answer 0.

A third important case is a strictly decreasing array such as [5,4,3,2,1]. The earliest balanced shipment is [5,4], after which the algorithm restarts and forms [3,2]. The final 1 cannot form a shipment by itself. The answer is therefore 2, demonstrating that immediately closing a shipment when it first becomes balanced maximizes the total count.

Finally, arrays containing repeated opportunities for short shipments, such as [10,1,10,1,10,1], test whether the algorithm preserves future opportunities. By ending each shipment at the earliest valid position, it obtains three shipments, which is the maximum possible number.