Optimal Weight Partition — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Optimal Weight Partition problem optimally.
O(n)O(1)Problem Description
You are given a non‑decreasing array weights of length n containing integer values. Choose an index k (0 ≤ k ≤ n) and split the array into a left part weights[0..k‑1] and a right part weights[k..n‑1]. Let S be the total sum of all elements and L(k) the sum of the left part. Your task is to find a split that makes L(k) as close as possible to S/2. If multiple splits yield the same minimal absolute difference, return the smaller L(k). Output that optimal left‑part sum.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Weight Partition"
WHY DOES IT MATTER?
The two‑pointer / prefix‑sum pattern turns a potentially quadratic search into a linear scan, a core skill for optimizing any problem that asks for a partition or balance point in a sorted or monotonic sequence.
OPTIMIZATION CHALLENGE
Recognizing that L(k) changes by exactly weights[k] when moving k by one step lets you update the difference to S/2 in constant time, eliminating the need for recomputation of sums at each index.
REAL-WORLD CONNECTION
Think of load‑balancing servers: you continuously add requests (weights) to the left side until the cumulative load is as close as possible to half of the total capacity, then you split traffic. The same incremental reasoning applies to partitioning data shards across nodes.
During an interview, compute the total sum first, then walk the array with a running prefix. Compare |2*prefix‑S| instead of floating‑point division to avoid precision issues and keep the code integer‑only.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for a split index k that makes the sum of the left partition L(k) as close as possible to half of the total sum S. A naïve solution would recompute L(k) for every possible k, leading to O(n^2) time because each prefix sum would be recomputed from scratch. The optimal paradigm leverages the monotonic nature of the prefix sums: as k increases, L(k) grows monotonically while the complementary right sum S‑L(k) shrinks. This monotonicity enables a two‑pointer or sliding‑window style scan where we maintain a running prefix sum and compare its distance to S/2 at each step, updating the best split in O(1) per element. By pre‑computing the total sum once and then iterating once through the array while updating the prefix sum, we achieve O(n) time and O(1) extra space, which scales to the largest input sizes typical in interview constraints.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain negative numbers?
With negatives the prefix sum is no longer monotonic, so the simple linear scan may miss the optimal split. You would need to store all prefix sums in a balanced BST or use binary search on a sorted list of prefix sums to find the value closest to S/2, yielding O(n log n) time.
Q2Can you extend the algorithm to return all split indices that achieve the minimal absolute difference?
Yes. While scanning, keep track of the current minimal difference. Whenever a new split matches that difference, add its index to a result list; if a smaller difference is found, clear the list and store the new index. This still runs in O(n) time and O(k) space for k optimal splits.
Q3What is the time‑space trade‑off if you need to answer multiple queries of the form ‘what split gives the closest sum to X?’ on the same array?
Pre‑compute the prefix sums array (O(n) space) and then for each query perform a binary search for X in the sorted prefix sums, achieving O(log n) per query with O(n) preprocessing space.
Examples
Input
[1,2,3,4,5]
Output
6
Explanation: Total sum S=15, half is 7.5. Prefix sums are 1,3,6,10,15. The distances to 7.5 are 6.5,4.5,1.5,2.5,7.5 respectively. The minimum distance is 1.5 at prefix sum 6, so the answer is 6.
Input
[2,2,2,2]
Output
4
Explanation: S=8, half=4. Prefix sums: 2,4,6,8. The prefix sum 4 matches the target exactly, giving distance 0. Hence the optimal left sum is 4.
Input
[5,10,15]
Output
15
Explanation: S=30, half=15. Prefix sums: 5,15,30. The second prefix sum equals the target, so the optimal left sum is 15.
Constraints
- 1 <= weights.length <= 200000
- -10^9 <= weights[i] <= 10^9
- weights is sorted in non‑decreasing order
- All calculations fit in 64‑bit signed integer
Optimal Approach & Strategy
Compute the total sum once, then iterate once while maintaining a running prefix sum, updating the best split in O(1) per element for O(n) total time.
Brute Force Approach
For each possible split index compute the left sum from scratch and track the minimal absolute difference, resulting in O(n^2) time.
Code Solutions
function optimalWeightPartition(weights) {
let total = weights.reduce((a, b) => a + b, 0);
let target = Math.trunc(total / 2); // truncates toward zero
let best = 0;
let minDiff = Infinity;
let cur = 0;
for (let w of weights) {
cur += w;
let diff = Math.abs(cur - target);
if (diff < minDiff) {
minDiff = diff;
best = cur;
}
}
return best;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let weights = [];
let n = 0;
rl.on('line', line => {
if (n === 0) {
n = parseInt(line);
} else {
weights.push(parseInt(line));
}
}).on('close', () => {
console.log(optimalWeightPartition(weights));
});
#include <iostream>
#include <vector>
#include <climits>
#include <cstdlib>
int optimalWeightPartition(std::vector<int>& weights) {
long long totalSum = 0;
for (int w : weights) totalSum += w;
long long target = totalSum / 2; // integer division truncates toward zero
long long bestSum = 0;
long long minDiff = LLONG_MAX;
long long cur = 0;
for (int w : weights) {
cur += w;
long long diff = std::llabs(cur - target);
if (diff < minDiff) {
minDiff = diff;
bestSum = cur;
}
}
return static_cast<int>(bestSum);
}
int main() {
std::vector<int> weights;
int n;
std::cin >> n;
for (int i = 0; i < n; ++i) {
int x; std::cin >> x; weights.push_back(x);
}
std::cout << optimalWeightPartition(weights) << "\n";
return 0;
}
import java.util.Scanner;
public class OptimalWeightPartition {
public static int optimalWeightPartition(int[] weights) {
long total = 0;
for (int w : weights) total += w;
long target = total / 2; // truncates toward zero
long best = 0;
long minDiff = Long.MAX_VALUE;
long cur = 0;
for (int w : weights) {
cur += w;
long diff = Math.abs(cur - target);
if (diff < minDiff) {
minDiff = diff;
best = cur;
}
}
return (int) best;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] weights = new int[n];
for (int i = 0; i < n; i++) weights[i] = sc.nextInt();
System.out.println(optimalWeightPartition(weights));
}
}
def optimal_weight_partition(weights):
total = sum(weights)
target = total // 2 # floor division works for positive and negative numbers as required
best = 0
min_diff = float('inf')
cur = 0
for w in weights:
cur += w
diff = abs(cur - target)
if diff < min_diff:
min_diff = diff
best = cur
return best
n = int(input())
weights = [int(input()) for _ in range(n)]
print(optimal_weight_partition(weights))
function optimalWeightPartition(weights) {
let total = weights.reduce((a, b) => a + b, 0);
let target = Math.trunc(total / 2); // truncates toward zero
let best = 0;
let minDiff = Infinity;
let cur = 0;
for (let w of weights) {
cur += w;
let diff = Math.abs(cur - target);
if (diff < minDiff) {
minDiff = diff;
best = cur;
}
}
return best;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let weights = [];
let n = 0;
rl.on('line', line => {
if (n === 0) {
n = parseInt(line);
} else {
weights.push(parseInt(line));
}
}).on('close', () => {
console.log(optimalWeightPartition(weights));
});
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.