Balanced Partitioning — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Balanced Partitioning problem optimally.
O(n)O(1)Problem Description
You are given two integer arrays weights and volumes, each of length n. Determine whether there exists an index i (0 ≤ i < n‑1) such that the sum of weights from 0 to i equals the sum of weights from i+1 to n‑1 and simultaneously the sum of volumes from 0 to i equals the sum of volumes from i+1 to n‑1. If such an index exists, return the smallest i; otherwise return -1. The algorithm must run in O(n) time and O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Partitioning"
WHY DOES IT MATTER?
Balancing two independent dimensions simultaneously appears in load‑balancing, financial portfolio partitioning, and multi‑resource scheduling, making the pattern a core tool for multi‑criteria decision making.
OPTIMIZATION CHALLENGE
Recognizing that the right‑hand sum can be expressed as total‑left eliminates the need for a nested loop; the transformation 2*leftSum==totalSum is the pivotal insight that collapses O(n^2) work into O(n).
REAL-WORLD CONNECTION
Think of a warehouse where you need to split inventory into two trucks so that both weight and volume are exactly equal – the algorithm tells you the exact cut point along a sorted loading order.
During an interview, compute total sums first, then iterate once keeping only two running totals – this avoids off‑by‑one errors and lets you return the smallest valid index immediately.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for a split index where two independent cumulative sums – one for weights and one for volumes – are simultaneously balanced. A naive solution would recompute prefix and suffix sums for each possible i, leading to O(n^2) time, which quickly becomes infeasible for large n (10^5 or more) because each recomputation scans a linear portion of the array. The optimal paradigm leverages prefix sums: by scanning the arrays once we can maintain running totals of the left side while the total sum of the whole array is known in advance, allowing us to derive the right‑side sum in O(1) for each i. This reduces the overall complexity to linear time, O(n), with constant extra space, which is the hallmark of two‑pointer or prefix‑sum techniques for partition‑type problems. The key insight is that the condition "left sum == right sum" can be rewritten as "2*left sum == total sum"; applying this simultaneously to both weight and volume arrays yields a simple constant‑time check at each index, making the algorithm both elegant and scalable.
Interview Questions on This Problem
Q1How would you modify the solution if the arrays could contain negative numbers?
The same prefix‑sum approach works because the equality check 2*leftSum==totalSum remains valid regardless of sign; you just need to compute total sums including negatives and perform the same O(n) scan.
Q2Can you solve the problem using a two‑pointer technique from both ends instead of prefix sums?
Yes; start pointers at the ends, maintain leftWeight/leftVolume and rightWeight/rightVolume sums, move the left pointer forward while the left sums are less than the right sums, and stop when both pairs match – this also runs in O(n) but is less straightforward than the prefix‑sum method.
Q3If the arrays are streamed and you cannot store them entirely, how would you determine the split index?
First pass to compute totalWeight and totalVolume (streaming aggregates). In a second pass, maintain running left sums and stop at the first i where 2*leftWeight==totalWeight and 2*leftVolume==totalVolume; this requires only O(1) extra memory and two linear passes over the stream.
Examples
Input
{"n":5,"weights":[2,3,2,5,2],"volumes":[4,2,3,6,3]}Output
2
Explanation: Total weight = 14, total volume = 18. Half of each is 7 and 9 respectively. Prefix sums up to index 2 give weight 2+3+2 = 7 and volume 4+2+3 = 9, matching the required halves, so index 2 is a valid partition point.
Input
{"n":4,"weights":[5,1,2,3],"volumes":[1,2,3,4]}Output
-1
Explanation: Total weight = 11, which is odd, so it cannot be split into two equal integer halves. Hence no index satisfies both conditions.
Input
{"n":6,"weights":[4,5,1,5,6,9],"volumes":[7,3,5,5,8,12]}Output
3
Explanation: Total weight = 30 and total volume = 40, half values are 15 and 20. Prefix sums up to index 3 give weight 4+5+1+5 = 15 and volume 7+3+5+5 = 20, fulfilling both equal‑half requirements; index 3 is the smallest such index.
Constraints
- 1 <= n <= 100000
- -10^9 <= weights[i] <= 10^9
- -10^9 <= volumes[i] <= 10^9
- All calculations fit in 64‑bit signed integer
Optimal Approach & Strategy
Compute total sums once, then scan once keeping running left sums and compare 2*leftSum to total, achieving O(n) time and O(1) extra space.
Brute Force Approach
For each possible split index recompute the left and right sums of both arrays from scratch, leading to O(n^2) time.
Code Solutions
function balancedPartition(weights, volumes) {
const n = weights.length;
if (n < 2) return -1;
let totalW = 0, totalV = 0;
for (let i = 0; i < n; ++i) {
totalW += weights[i];
totalV += volumes[i];
}
let prefW = 0, prefV = 0;
for (let i = 0; i < n - 1; ++i) {
prefW += weights[i];
prefV += volumes[i];
if (prefW * 2 === totalW && prefV * 2 === totalV) return i;
}
return -1;
}
// Driver (Node.js)
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++] || 0;
const weights = data.slice(p, p + n); p += n;
const volumes = data.slice(p, p + n);
console.log(balancedPartition(weights, volumes).toString());#include <bits/stdc++.h>
using namespace std;
int balancedPartition(const vector<int>& weights, const vector<int>& volumes) {
int n = (int)weights.size();
if (n < 2) return -1;
long long totalW = 0, totalV = 0;
for (int w : weights) totalW += w;
for (int v : volumes) totalV += v;
long long prefW = 0, prefV = 0;
for (int i = 0; i < n - 1; ++i) {
prefW += weights[i];
prefV += volumes[i];
if (prefW * 2 == totalW && prefV * 2 == totalV) return i;
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> weights(n), volumes(n);
for(int i=0;i<n;++i) cin>>weights[i];
for(int i=0;i<n;++i) cin>>volumes[i];
cout<<balancedPartition(weights, volumes);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static int balancedPartition(int[] weights, int[] volumes) {
int n = weights.length;
if (n < 2) return -1;
long totalW = 0, totalV = 0;
for (int w : weights) totalW += w;
for (int v : volumes) totalV += v;
long prefW = 0, prefV = 0;
for (int i = 0; i < n - 1; ++i) {
prefW += weights[i];
prefV += volumes[i];
if (prefW * 2 == totalW && prefV * 2 == totalV) return i;
}
return -1;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int[] weights = new int[n];
int[] volumes = new int[n];
for (int i = 0; i < n; i++) weights[i] = fs.nextInt();
for (int i = 0; i < n; i++) volumes[i] = fs.nextInt();
System.out.print(balancedPartition(weights, volumes));
}
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream in) { this.in = in; }
private int readByte() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sign = 1, val = 0;
do { c = readByte(); } while (c <= ' ' && c != -1);
if (c == '-') { sign = -1; c = readByte(); }
while (c > ' ') {
val = val * 10 + (c - '0');
c = readByte();
}
return val * sign;
}
}
}def balanced_partition(weights, volumes):
n = len(weights)
if n < 2:
return -1
total_w = sum(weights)
total_v = sum(volumes)
pref_w = pref_v = 0
for i in range(n - 1):
pref_w += weights[i]
pref_v += volumes[i]
if pref_w * 2 == total_w and pref_v * 2 == total_v:
return i
return -1
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
sys.exit()
n = data[0]
weights = data[1:1+n]
volumes = data[1+n:1+2*n]
print(balanced_partition(weights, volumes))function balancedPartition(weights, volumes) {
const n = weights.length;
if (n < 2) return -1;
let totalW = 0, totalV = 0;
for (let i = 0; i < n; ++i) {
totalW += weights[i];
totalV += volumes[i];
}
let prefW = 0, prefV = 0;
for (let i = 0; i < n - 1; ++i) {
prefW += weights[i];
prefV += volumes[i];
if (prefW * 2 === totalW && prefV * 2 === totalV) return i;
}
return -1;
}
// Driver (Node.js)
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let p = 0;
const n = data[p++] || 0;
const weights = data.slice(p, p + n); p += n;
const volumes = data.slice(p, p + n);
console.log(balancedPartition(weights, volumes).toString());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.