Balanced Subarray Length — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Balanced Subarray Length problem optimally.
O(n^2)O(n)Problem Description
Given a non‑decreasing integer array weights, determine the maximum possible length of a contiguous subarray that can be split exactly in the middle such that the sum of the elements in the left half equals the sum of the elements in the right half. The subarray must have even length because the split occurs between two central elements. Return the length of the longest such subarray; if no valid subarray exists, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Subarray Length"
WHY DOES IT MATTER?
Balanced‑subarray problems capture the essence of prefix‑sum manipulation and equality constraints, a pattern that recurs in load‑balancing, financial reconciliation, and memory‑segmentation checks. Mastery of this pattern sharpens a candidate’s ability to turn a quadratic condition into constant‑time checks.
OPTIMIZATION CHALLENGE
The key insight is the algebraic rewrite 2*prefix[mid+1] = prefix[l] + prefix[r+1]. By moving from element‑wise summation to a relationship between three prefix values, we eliminate the inner O(length) loop and achieve O(1) verification per window.
REAL-WORLD CONNECTION
Think of a distributed log replication system where two consecutive shards must hold identical cumulative data size for consistency. Verifying the longest stretch where the left shard’s size equals the right shard’s mirrors the balanced subarray check.
When coding, first build the prefix‑sum array, then loop over possible even lengths from largest to smallest. As soon as you find a valid window you can break – this early‑exit often saves a factor of two in practice.
COMPLEXITY AT A GLANCE
O(n^2)O(n)Core Theory — Why This Approach?
The problem asks for the longest even‑length contiguous segment whose left half and right half have identical sums. A naïve solution would enumerate every possible subarray, compute its two half‑sums and check equality – this is O(n³) because each subarray requires O(length) work. By pre‑computing a prefix‑sum array we can obtain any subarray sum in O(1). The condition sum[l..mid] = sum[mid+1..r] transforms into 2*prefix[mid+1] = prefix[l] + prefix[r+1]. This algebraic form enables us to replace the inner linear scan with constant‑time arithmetic, reducing the enumeration to O(n²): we iterate over all possible even lengths (or all possible split points) and slide a window, checking the equality with a single arithmetic expression. The optimal paradigm therefore combines prefix‑sum preprocessing with a double‑loop that leverages the derived equality, achieving quadratic time while using only O(n) auxiliary space for the prefix array.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain negative numbers and you needed the longest subarray where the *difference* between the left and right half sums is at most k?
Compute prefix sums as before, but for each split index m store the value key = 2*prefix[m] . While sliding a window you need to find the farthest l and r such that |(prefix[l] + prefix[r+1]) - 2*prefix[m]| ≤ k. This can be answered in O(log n) per split using a balanced BST (e.g., TreeMap) that indexes prefix values, turning the overall complexity into O(n log n).
Q2A fintech platform stores transaction amounts in a non‑decreasing array. Explain how the balanced‑subarray length algorithm can be used to detect a suspicious pattern where two consecutive periods have equal total transaction volume.
Treat each period as a half of a candidate subarray. The algorithm finds the longest even‑length window where the sum of the first half equals the sum of the second half, directly revealing the longest span of consecutive days with matching transaction totals – a pattern that may indicate automated or split transactions.
Q3In a high‑growth startup, you need to run this check on streaming data where the array grows over time. Which data structure would let you maintain the answer incrementally?
Maintain a rolling prefix‑sum and a hash map that records, for each possible split point, the earliest index where a particular value of 2*prefix[m] was seen. When a new element arrives, update the prefix, recompute 2*prefix for the new split, and check the map for matching earlier prefix values to potentially extend the longest balanced subarray in O(1) amortized time.
Examples
Input
[1,2,3,3,4,5,6]
Output
2
Explanation: The only contiguous pair with equal sums is the adjacent 3s at indices 3 and 4. Their subarray [3,3] has left sum 3 and right sum 3, giving length 2. No longer even‑length subarray satisfies the condition, so the answer is 2.
Input
[2,2,2,2,2]
Output
4
Explanation: Any even‑length segment of this array has identical elements, so the sums of the two halves are always equal. The longest even length not exceeding the array size is 4 (indices 0 to 3 or 1 to 4). Hence the answer is 4.
Input
[-3,-1,0,0,1,3]
Output
2
Explanation: The subarray [0,0] (indices 2 and 3) yields left sum 0 and right sum 0, giving a valid length of 2. All other even‑length subarrays have mismatched half‑sums, so the maximum length is 2.
Constraints
- 1 <= weights.length <= 100000
- -10^9 <= weights[i] <= 10^9
- weights is sorted in non‑decreasing order
Optimal Approach & Strategy
Build a prefix‑sum array and for each possible split point evaluate the equality 2*prefix[mid] = prefix[l] + prefix[r] in O(1), sliding a window over all even lengths to find the maximum.
Brute Force Approach
Enumerate every even‑length subarray, compute the two half‑sums by iterating over the elements, and keep the longest that matches.
Code Solutions
function balancedSubarrayLength(weights) {
const n = weights.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) pref[i + 1] = pref[i] + weights[i];
for (let len = n; len >= 2; --len) {
if (len % 2 !== 0) continue; // even length only
const half = len / 2;
for (let i = 0; i + len <= n; ++i) {
const left = pref[i + half] - pref[i];
const right = pref[i + len] - pref[i + half];
if (left === right) return len;
}
}
return 0;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let lines = [];
rl.on('line', line => { lines.push(line.trim()); })
.on('close', () => {
const n = parseInt(lines[0] || '0');
const weights = lines[1] ? lines[1].split(/\s+/).map(Number) : [];
console.log(balancedSubarrayLength(weights));
});
#include <iostream>
#include <vector>
int balancedSubarrayLength(const std::vector<int>& weights) {
int n = weights.size();
// prefix sums: pref[i] = sum of first i elements (pref[0] = 0)
std::vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + weights[i];
for (int len = n; len >= 2; --len) {
if (len % 2) continue; // need even length
int half = len / 2;
for (int i = 0; i + len <= n; ++i) {
long long left = pref[i + half] - pref[i];
long long right = pref[i + len] - pref[i + half];
if (left == right) return len;
}
}
return 0;
}
int main() {
int n;
std::cin >> n;
std::vector<int> weights(n);
for (int i = 0; i < n; ++i) std::cin >> weights[i];
std::cout << balancedSubarrayLength(weights) << std::endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int balancedSubarrayLength(int[] weights) {
int n = weights.length;
long[] pref = new long[n + 1];
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + weights[i];
for (int len = n; len >= 2; --len) {
if ((len & 1) == 1) continue; // need even length
int half = len / 2;
for (int i = 0; i + len <= n; ++i) {
long left = pref[i + half] - pref[i];
long right = pref[i + len] - pref[i + half];
if (left == right) return len;
}
}
return 0;
}
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(balancedSubarrayLength(weights));
}
}
def balanced_subarray_length(weights):
n = len(weights)
# prefix sums
pref = [0] * (n + 1)
for i in range(n):
pref[i + 1] = pref[i] + weights[i]
for length in range(n, 1, -1):
if length % 2:
continue
half = length // 2
for i in range(n - length + 1):
left = pref[i + half] - pref[i]
right = pref[i + length] - pref[i + half]
if left == right:
return length
return 0
def main():
n = int(input())
weights = list(map(int, input().split())) if n else []
print(balanced_subarray_length(weights))
if __name__ == "__main__":
main()
function balancedSubarrayLength(weights) {
const n = weights.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) pref[i + 1] = pref[i] + weights[i];
for (let len = n; len >= 2; --len) {
if (len % 2 !== 0) continue; // even length only
const half = len / 2;
for (let i = 0; i + len <= n; ++i) {
const left = pref[i + half] - pref[i];
const right = pref[i + len] - pref[i + half];
if (left === right) return len;
}
}
return 0;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let lines = [];
rl.on('line', line => { lines.push(line.trim()); })
.on('close', () => {
const n = parseInt(lines[0] || '0');
const weights = lines[1] ? lines[1].split(/\s+/).map(Number) : [];
console.log(balancedSubarrayLength(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.