mediumTwo PointersPattern: Mixed
Optimal Weight Partition Solution
Problem Statement
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
Example 1:
Input:{"weights":[1,2,3,4,5]}
Output:3
Explanation: The total weight is 15. To split it as close to half as possible, the first part should be 1 + 2 + 3 + 4 = 10, and the second part should be 5. The split index is 3 (0-based index for the start of the second part), but since the problem asks for the index at which the split can be done, we consider the index 3.
Example 2:
Input:{"weights":[10,20,30,40,50]}
Output:5
Explanation: The total weight is 150. To split it as close to half as possible, the first part should be 10 + 20 + 30 + 40 + 50 = 150, but this is not possible since we have to split the array into two parts. The closest we can get to half is by splitting at the index where the total weight of the first part is less than half and the total weight of the second part is more than half. The total weight of the first part (10 + 20 + 30) is 60 and the total weight of the second part (40 + 50) is 90. Thus, we can split at index 3.
Constraints
- {"name":"weights length","description":"1 <= weights.length <= 10^5"}
- {"name":"weights values","description":"1 <= weights[i] <= 10^5"}
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.