Partition Array by Weight — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
First compute the total sum, then scan once keeping a running left sum; compare left sum with total‑left sum at each step.
O(n)O(1)Problem Description
Given an array weights of non‑negative integers, determine whether there exists an index i (0 ≤ i ≤ n) such that the sum of all elements strictly before i equals the sum of all elements from i to the end of the array. The index may be at the very start (i = 0) or at the very end (i = n), meaning an empty prefix or suffix is allowed. Return true if at least one such split exists, otherwise return false.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Partition Array by Weight"
WHY DOES IT MATTER?
The prefix‑sum pattern is a cornerstone for any problem that asks for a balance point, enabling O(n) solutions where brute force would be prohibitive. Mastery of this pattern unlocks efficient solutions for load‑balancing, memory partitioning, and financial reconciliation tasks.
OPTIMIZATION CHALLENGE
Realizing that the right‑hand sum can be expressed as totalSum‑leftSum eliminates the need for a second nested loop. The key insight is that the total sum is constant, so updating the left sum incrementally gives the right sum instantly.
REAL-WORLD CONNECTION
Think of a warehouse conveyor belt where packages are loaded onto two trucks. The goal is to find a point where the weight loaded onto the first truck equals the weight remaining for the second truck – you only need the cumulative weight as you move along, not recompute from scratch each time.
During an interview, compute totalSum first, then walk the array updating leftSum. As soon as leftSum equals totalSum‑leftSum, return true. Remember to handle the empty‑prefix/empty‑suffix cases by checking totalSum == 0.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for a split index where the prefix sum equals the suffix sum. A naïve solution would recompute the sum of the left and right parts for every possible i, leading to O(n^2) time, which quickly becomes infeasible for large n (e.g., n ≈ 10^5). The optimal paradigm leverages the prefix‑sum technique: by scanning the array once while maintaining a running total of the elements seen so far, we can compute the left sum in O(1) per index. The right sum is simply totalSum‑leftSum, so we only need a single pass after computing totalSum, yielding O(n) time and O(1) extra space. This approach exemplifies the “running total / two‑pointer” pattern that turns many partition‑type problems from quadratic to linear time.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain negative numbers and you needed the split index where the absolute difference between prefix and suffix sums is minimized?
First compute the total sum, then iterate while tracking the prefix sum. At each index compute diff = Math.abs(prefix - (total‑prefix)). Keep the minimum diff and its index. This still runs in O(n) time and O(1) space.
Q2In a distributed system where the array is sharded across multiple nodes, how can you determine a global split point without moving all data to a single node?
Each node computes its local sum and reports it. A coordinator aggregates these to obtain the global total, then performs a second pass where nodes stream their elements in order, maintaining a running global prefix until prefix equals total‑prefix, identifying the split without full data migration.
Q3Why is it safe to return true when i = 0 or i = n, and how does this affect edge‑case handling in code?
i = 0 means an empty prefix (sum = 0) and i = n means an empty suffix (sum = 0). If totalSum is 0, both conditions are satisfied, so the algorithm must explicitly check for totalSum == 0 before the loop or allow the loop to handle i = n by comparing after the final iteration.
Examples
Input
[1,2,3,6]
Output
true
Explanation: Total sum = 12. For i = 3, prefix sum = 1+2+3 = 6 and suffix sum = 6. Both are equal, so the answer is true.
Input
[0,0,0]
Output
true
Explanation: Total sum = 0. Any index yields prefix sum = suffix sum = 0. Hence a valid split exists and the answer is true.
Input
[1,5,3]
Output
false
Explanation: Total sum = 9. Prefix/suffix sums for i=0..3 are (0,9), (1,8), (6,3), (9,0). No pair matches, so the answer is false.
Constraints
- 1 <= weights.length <= 100000
- 0 <= weights[i] <= 10^9
- All calculations fit in 64‑bit signed integer
Optimal Approach & Strategy
First compute the total sum, then scan once keeping a running left sum; compare left sum with total‑left sum at each step.
Brute Force Approach
For each possible split index recompute the sum of the left part and the sum of the right part, then compare them.
Code Solutions
function canSplit(weights) {
let total = 0;
for (const w of weights) total += w;
let prefix = 0;
if (prefix * 2 === total) return true; // i = 0
for (let i = 0; i < weights.length; ++i) {
prefix += weights[i];
if (prefix * 2 === total) return true;
}
return false;
}
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++] || 0;
const weights = data.slice(idx, idx + n);
console.log(canSplit(weights) ? "true" : "false");#include <bits/stdc++.h>
using namespace std;
bool canSplit(const vector<int>& weights) {
long long total = 0;
for (int w : weights) total += w;
long long prefix = 0;
// Check i = 0
if (prefix * 2 == total) return true;
for (size_t i = 0; i < weights.size(); ++i) {
prefix += weights[i];
if (prefix * 2 == total) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if(!(cin>>n)) return 0;
vector<int> weights(n);
for(int i=0;i<n;++i) cin>>weights[i];
cout << (canSplit(weights) ? "true" : "false");
return 0;
}import java.io.*;
import java.util.*;
public class Main {
public static boolean canSplit(int[] weights) {
long total = 0;
for (int w : weights) total += w;
long prefix = 0;
if (prefix * 2 == total) return true; // i = 0
for (int w : weights) {
prefix += w;
if (prefix * 2 == total) return true;
}
return false;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if (line == null || line.isEmpty()) {
System.out.print("true");
return;
}
int n = Integer.parseInt(line.trim());
int[] weights = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
while (!st.hasMoreTokens()) {
st = new StringTokenizer(br.readLine());
}
weights[i] = Integer.parseInt(st.nextToken());
}
System.out.print(canSplit(weights) ? "true" : "false");
}
}def can_split(weights):
total = sum(weights)
prefix = 0
if prefix * 2 == total:
return True # i = 0
for w in weights:
prefix += w
if prefix * 2 == total:
return True
return False
if __name__ == "__main__":
import sys
data = list(map(int, sys.stdin.read().strip().split()))
if not data:
print("true")
else:
n = data[0]
weights = data[1:1+n]
print("true" if can_split(weights) else "false")function canSplit(weights) {
let total = 0;
for (const w of weights) total += w;
let prefix = 0;
if (prefix * 2 === total) return true; // i = 0
for (let i = 0; i < weights.length; ++i) {
prefix += weights[i];
if (prefix * 2 === total) return true;
}
return false;
}
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++] || 0;
const weights = data.slice(idx, idx + n);
console.log(canSplit(weights) ? "true" : "false");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.