Skip to content

3638. Maximum Balanced Shipments

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.

 

Example 1:

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

Output: 2

Explanation:

We can form the maximum of two balanced shipments as follows:

  • Shipment 1: [2, 5, 1]
    • Maximum parcel weight = 5
    • Last parcel weight = 1, which is strictly less than 5. Thus, it's balanced.
  • Shipment 2: [4, 3]
    • Maximum parcel weight = 4
    • Last parcel weight = 3, which is strictly less than 4. Thus, it's balanced.

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:

  • A shipment [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.
  • Single-parcel shipments [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 <= 105
  • 1 <= weight[i] <= 109

Solutions

Solution 1: Greedy

We maintain the maximum value \(\text{mx}\) of the currently traversed array, and iterate through each element \(x\) in the array. If \(x < \text{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 \(\text{mx}\) to 0. Otherwise, we update \(\text{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.

1
2
3
4
5
6
7
8
9
class Solution:
    def maxBalancedShipments(self, weight: List[int]) -> int:
        ans = mx = 0
        for x in weight:
            mx = max(mx, x)
            if x < mx:
                ans += 1
                mx = 0
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int maxBalancedShipments(int[] weight) {
        int ans = 0;
        int mx = 0;
        for (int x : weight) {
            mx = Math.max(mx, x);
            if (x < mx) {
                ++ans;
                mx = 0;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxBalancedShipments(vector<int>& weight) {
        int ans = 0;
        int mx = 0;
        for (int x : weight) {
            mx = max(mx, x);
            if (x < mx) {
                ++ans;
                mx = 0;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func maxBalancedShipments(weight []int) (ans int) {
    mx := 0
    for _, x := range weight {
        mx = max(mx, x)
        if x < mx {
            ans++
            mx = 0
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maxBalancedShipments(weight: number[]): number {
    let [ans, mx] = [0, 0];
    for (const x of weight) {
        mx = Math.max(mx, x);
        if (x < mx) {
            ans++;
            mx = 0;
        }
    }
    return ans;
}

Comments