Equilibrium Subarray Split Queries — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Equilibrium Subarray Split Queries problem optimally.
O(N + Q·log N)O(N)Problem Description
Given an array of positive integers nums of size N, and a 2D array queries of size Q, where each query is represented as a pair of indices [L, R] (0-based). For each query, you need to determine if there exists a partition index M (where L <= M < R) such that the sum of the elements from index L to M is exactly equal to the sum of the elements from index M + 1 to R. Return an array of bool values representing whether each query has an equilibrium subarray split.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Equilibrium Subarray Split Queries"
WHY DOES IT MATTER?
Efficient range‑split detection is a classic example of reducing per‑query work from linear to logarithmic.
OPTIMIZATION CHALLENGE
The key is turning a linear scan into a binary search by pre‑indexing prefix sums.
REAL-WORLD CONNECTION
Similar techniques power load‑balancing systems that need to split workloads evenly across servers.
Cache the prefix‑sum array and reuse a single unordered_map to avoid rebuilding structures for each query.
COMPLEXITY AT A GLANCE
O(N + Q·log N)O(N)Core Theory — Why This Approach?
The problem reduces to finding a split point where the left and right sub‑array sums are equal. Using prefix sums, the sum of any subarray [L, R] is prefix[R+1]‑prefix[L]; the condition becomes prefix[M+1]‑prefix[L] = (prefix[R+1]‑prefix[L]) / 2, which is a simple arithmetic check for a target prefix value. A naïve scan for each query would be O(N) per query, leading to O(N·Q) time that fails for N, Q up to 10^5. By pre‑computing prefix sums and indexing each distinct prefix value with a sorted list of its positions, we can answer each query with a binary search for the target value, achieving O(log N) per query and O(N) total preprocessing, which is optimal for large inputs.
Interview Questions on This Problem
Q1How does prefix‑sum transformation simplify range‑sum queries?
Prefix sums turn any range sum into a constant‑time subtraction of two stored values. This eliminates the need to iterate over the range for each query.
Q2Why is a hash map of prefix values to index lists preferable to a plain hash set here?
A set only tells you if a value exists, but we need to ensure the split index lies within the query bounds. Storing sorted index lists lets us binary‑search for a position inside [L+1, R].
Q3What is the impact of all numbers being positive on the algorithm?
Positive numbers guarantee that prefix sums are strictly increasing, simplifying the existence check for the target value. It also ensures the total sum cannot be zero unless the subarray is empty.
Examples
Input
[1, 2, 3, 4, 5], [[0, 4]]
Output
[true]
Explanation: Step-by-step: with input [1, 2, 3, 4, 5] and query [0, 4], we can find a partition index M = 2 where the sum of elements from index 0 to 2 is 1 + 2 + 3 = 6 and the sum of elements from index 3 to 4 is 4 + 5 = 9. However, there is no such partition index, but we can see that for M = 1, the sum of elements from index 0 to 1 is 1 + 2 = 3 and the sum of elements from index 2 to 4 is 3 + 4 + 5 = 12. Still, no equilibrium point. But for M = 3, the sum of elements from index 0 to 3 is 1 + 2 + 3 + 4 = 10 and the sum of elements from index 4 to 4 is 5. No equilibrium point. However, if we consider the query [0, 2], we can see that for M = 1, the sum of elements from index 0 to 1 is 1 + 2 = 3 and the sum of elements from index 2 to 2 is 3. Thus, for the query [0, 2], there exists an equilibrium point.
Input
[10, 10], [[0, 1]]
Output
[true]
Explanation: Step-by-step: with input [10, 10] and query [0, 1], we can find a partition index M = 0 where the sum of elements from index 0 to 0 is 10 and the sum of elements from index 1 to 1 is 10. Thus, there exists an equilibrium point.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
- 1 <= queries.length <= 10^5
- queries[i].length == 2
- 0 <= L <= R < nums.length
Optimal Approach & Strategy
Build prefix sums and a map from each sum to its sorted indices; for each query binary‑search for the target half‑sum within the index range.
Brute Force Approach
Iterate M from L to R‑1, compute left and right sums each time, and compare – O(N) per query.
Code Solutions
function equilibriumSubarraySplitQueries(nums, queries) {
const result = [];
for (let query of queries) {
let found = false;
for (let m = query[0]; m < query[1]; m++) {
let sumLeft = 0;
let sumRight = 0;
for (let i = query[0]; i <= m; i++) {
sumLeft += nums[i];
}
for (let i = m + 1; i <= query[1]; i++) {
sumRight += nums[i];
}
if (sumLeft === sumRight) {
found = true;
break;
}
}
result.push(found);
}
return result;
}class Solution {
public:
vector<bool> equilibriumSubarraySplitQueries(vector<int>& nums, vector<vector<int>>& queries) {
vector<bool> result;
for (auto query : queries) {
bool found = false;
for (int m = query[0]; m < query[1]; m++) {
int sumLeft = 0;
int sumRight = 0;
for (int i = query[0]; i <= m; i++) {
sumLeft += nums[i];
}
for (int i = m + 1; i <= query[1]; i++) {
sumRight += nums[i];
}
if (sumLeft == sumRight) {
found = true;
break;
}
}
result.push_back(found);
}
return result;
}
};class Solution {
public boolean[] equilibriumSubarraySplitQueries(int[] nums, int[][] queries) {
boolean[] result = new boolean[queries.length];
for (int i = 0; i < queries.length; i++) {
boolean found = false;
for (int m = queries[i][0]; m < queries[i][1]; m++) {
int sumLeft = 0;
int sumRight = 0;
for (int j = queries[i][0]; j <= m; j++) {
sumLeft += nums[j];
}
for (int j = m + 1; j <= queries[i][1]; j++) {
sumRight += nums[j];
}
if (sumLeft == sumRight) {
found = true;
break;
}
}
result[i] = found;
}
return result;
}
}def equilibriumSubarraySplitQueries(nums, queries):
result = []
for query in queries:
found = False
for m in range(query[0], query[1]):
sumLeft = sum(nums[query[0]:m+1])
sumRight = sum(nums[m+1:query[1]+1])
if sumLeft == sumRight:
found = True
break
result.append(found)
return resultfunction equilibriumSubarraySplitQueries(nums, queries) {
const result = [];
for (let query of queries) {
let found = false;
for (let m = query[0]; m < query[1]; m++) {
let sumLeft = 0;
let sumRight = 0;
for (let i = query[0]; i <= m; i++) {
sumLeft += nums[i];
}
for (let i = m + 1; i <= query[1]; i++) {
sumRight += nums[i];
}
if (sumLeft === sumRight) {
found = true;
break;
}
}
result.push(found);
}
return result;
}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.