Equilibrium Subarray Split Queries — Problem Statement & Solution Guide
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.
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
Precompute a prefix sum array in O(N). For each query [L, R], calculate the range sum; if it is odd, return false immediately. Otherwise, use binary search to locate the index M in the prefix sum array that corresponds to the target midpoint value in O(log N) time.
Brute Force Approach
Iterate through every possible split point M between L and R for each query. For each M, calculate the sum of the left subarray and the right subarray, checking if they are equal, which results in O(Q * N) time complexity.
Verified 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.