Optimal Weight Partition — Problem Statement & Solution Guide
Problem Description
Given a sorted array of integers weights, partition the array into two parts such that the sum of the weights in the first part is as close to half the total sum as possible. The partition can be done at any index.
Examples
Input
[21, 21, 21, 21, 21]
Output
2
Explanation: Step-by-step: with input [21, 21, 21, 21, 21], we calculate the total sum (105) and half of it (52.5). We then use two pointers to find the partition point. The first pointer starts at the beginning of the array, and the second pointer starts at the end. We move the first pointer to the right and the second pointer to the left until the sum of the weights in the first part is as close to half the total sum as possible. In this case, the partition point is at index 2, where the sum of the weights in the first part is 42, which is as close to half the total sum (52.5) as possible.
Input
[210, 210, 210, 210, 210, 210, 210, 210, 210, 210]
Output
4
Explanation: Step-by-step: with input [210, 210, 210, 210, 210, 210, 210, 210, 210, 210], we calculate the total sum (1890) and half of it (945). We then use two pointers to find the partition point. The first pointer starts at the beginning of the array, and the second pointer starts at the end. We move the first pointer to the right and the second pointer to the left until the sum of the weights in the first part is as close to half the total sum as possible. In this case, the partition point is at index 4, where the sum of the weights in the first part is 945, which is exactly half of the total sum (1890).
Constraints
- {"name":"weights length","description":"1 <= weights.length <= 10^5"}
- {"name":"weights values","description":"1 <= weights[i] <= 10^5"}
Optimal Approach & Strategy
The optimal approach involves calculating the total weight of all food items and then iterating through the array to find a split point that divides this total weight roughly in half. This approach has a time complexity of O(n) since we only need to iterate through the array once.
Brute Force Approach
The brute-force approach involves trying all possible split points and calculating the total weight of the first part for each split point. This would result in a time complexity of O(n^2) due to the nested loops. The brute-force approach is not efficient for large arrays.
Verified Code Solutions
function optimalWeightPartition(weights) {
let totalSum = 0;
for (let i = 0; i < weights.length; i++) {
totalSum += weights[i];
}
let targetSum = Math.floor(totalSum / 2);
let leftSum = 0;
let minDiff = Infinity;
let result = 0;
for (let i = 0; i < weights.length; i++) {
leftSum += weights[i];
let rightSum = totalSum - leftSum;
let diff = Math.abs(leftSum - targetSum);
if (diff < minDiff) {
minDiff = diff;
result = i + 1;
}
}
return result;
}class Solution {
public int optimalWeightPartition(int[] weights) {
int totalSum = 0;
for (int weight : weights) {
totalSum += weight;
}
int halfSum = totalSum / 2;
int leftSum = 0;
for (int i = 0; i < weights.length; i++) {
leftSum += weights[i];
if (leftSum == halfSum) {
return i;
} else if (leftSum > halfSum) {
return i - 1;
}
}
return weights.length - 1;
}
}def optimal_weight_partition(weights):
total_sum = sum(weights)
half_sum = total_sum // 2
left_sum = 0
for i, weight in enumerate(weights):
left_sum += weight
if left_sum == half_sum:
return i
elif left_sum > half_sum:
return i - 1
return len(weights) - 1function optimalWeightPartition(weights) {
let totalSum = 0;
for (let i = 0; i < weights.length; i++) {
totalSum += weights[i];
}
let targetSum = Math.floor(totalSum / 2);
let leftSum = 0;
let minDiff = Infinity;
let result = 0;
for (let i = 0; i < weights.length; i++) {
leftSum += weights[i];
let rightSum = totalSum - leftSum;
let diff = Math.abs(leftSum - targetSum);
if (diff < minDiff) {
minDiff = diff;
result = i + 1;
}
}
return result;
}Asked in Top Tech Interviews
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.