Balanced Cargo Partitioning — Problem Statement & Solution Guide
Problem Description
A logistics company needs to split a sequence of cargo packages on a conveyor belt into two non-empty contiguous sections: a Left Zone and a Right Zone. The weight of each package is represented by an integer array. To optimize shipping container loads, the warehouse manager wants to choose a split point such that the absolute difference between the total weight of the Left Zone and the total weight of the Right Zone is a multiple of k. If no such split exists, return -1.
Examples
Input
[1, 2, 3, 4, 5]
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we can split the array into [1, 2, 3] and [4, 5], resulting in a difference of |6 - 9| = 3, which is the minimum difference.
Input
[1, 1, 1, 1, 1]
Output
-1
Explanation: Step-by-step: with input [1, 1, 1, 1, 1], no matter how we split the array, the difference will always be even, but since k is not provided, we cannot determine if the difference is a multiple of k, so we return -1.
Constraints
- 2 <= weights.length <= 10^5
- 1 <= weights[i] <= 10^4
- 1 <= k <= 10^5
Optimal Approach & Strategy
The optimized approach first calculates the total sum of the array, S, in a single pass. Then, we iterate through the array while maintaining a running prefix sum, L, representing the Left Zone. The Right Zone's sum is simply S - L, allowing us to evaluate the difference |2L - S| % k == 0 in O(1) time per split, resulting in an overall O(n) time complexity and O(1) auxiliary space.
Brute Force Approach
The brute-force approach involves iterating through all possible split indices from 0 to n-2. For each split, we calculate the sum of the elements to the left and the sum of the elements to the right by iterating over both subarrays. This results in an O(n^2) time complexity because we recalculate the sums from scratch at every step.
Verified Code Solutions
function solution(nums, k) {
let minDiff = Infinity;
for (let i = 1; i < nums.length; i++) {
let leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0);
let rightSum = nums.slice(i).reduce((a, b) => a + b, 0);
let diff = Math.abs(leftSum - rightSum);
if (diff % k === 0 && diff < minDiff) {
minDiff = diff;
}
}
return minDiff === Infinity ? -1 : minDiff;
}class Solution {
public:
int solution(vector<int>& nums, int k) {
int minDiff = INT_MAX;
for (int i = 1; i < nums.size(); i++) {
int leftSum = 0;
int rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i; j < nums.size(); j++) {
rightSum += nums[j];
}
int diff = abs(leftSum - rightSum);
if (diff % k == 0 && diff < minDiff) {
minDiff = diff;
}
}
return minDiff == INT_MAX ? -1 : minDiff;
}
};class Solution {
public int solution(int[] nums, int k) {
int minDiff = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
int leftSum = 0;
int rightSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
for (int j = i; j < nums.length; j++) {
rightSum += nums[j];
}
int diff = Math.abs(leftSum - rightSum);
if (diff % k == 0 && diff < minDiff) {
minDiff = diff;
}
}
return minDiff == Integer.MAX_VALUE ? -1 : minDiff;
}
}def solution(nums, k):
min_diff = float('inf')
for i in range(1, len(nums)):
left_sum = sum(nums[:i])
right_sum = sum(nums[i:])
diff = abs(left_sum - right_sum)
if diff % k == 0 and diff < min_diff:
min_diff = diff
return -1 if min_diff == float('inf') else min_difffunction solution(nums, k) {
let minDiff = Infinity;
for (let i = 1; i < nums.length; i++) {
let leftSum = nums.slice(0, i).reduce((a, b) => a + b, 0);
let rightSum = nums.slice(i).reduce((a, b) => a + b, 0);
let diff = Math.abs(leftSum - rightSum);
if (diff % k === 0 && diff < minDiff) {
minDiff = diff;
}
}
return minDiff === Infinity ? -1 : minDiff;
}Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.