Range Equilibrium Pivot — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Cumulative sum for range queries
O(n + q log n)O(n)Problem Description
Given an integer array nums and a 2D array of queries queries where queries[i] = [L, R], find the smallest index P (L <= P <= R) such that the sum of the elements in the subarray from index L to P - 1 is equal to the sum of the elements in the subarray from index P + 1 to R. If no such index exists, return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Range Equilibrium Pivot"
WHY DOES IT MATTER?
This pattern demonstrates how to convert a seemingly dynamic range condition into a static equality check, enabling fast queries after a single linear pass. It showcases the power of prefix sums and hashing to reduce per‑query work from linear to logarithmic, a technique widely used in competitive programming and production systems.
OPTIMIZATION CHALLENGE
The key insight is the algebraic manipulation that isolates the index‑dependent term 2·prefixSum[P‑1] + nums[P] and turns the problem into a constant‑time equality check per query, eliminating the need to scan the range.
REAL-WORLD CONNECTION
Think of a distributed log system where each server stores cumulative bytes written. To find a checkpoint where the left and right halves of a log segment have equal bytes, you pre‑compute cumulative sizes and then query for a target value. The same idea of turning a range sum equality into a lookup applies to load balancing and data sharding.
When explaining this to an interviewer, emphasize the two‑step process: (1) preprocess prefix sums and the val array, (2) answer queries by binary searching a sorted list of indices for each val. Highlight that the sorted lists can be built in O(n) by iterating once and appending indices, keeping the overall space linear.
COMPLEXITY AT A GLANCE
O(n + q log n)O(n)Core Theory — Why This Approach?
The problem is a classic example of transforming a range query into a constant‑time lookup by precomputing prefix sums. A naive approach would iterate over every index in the query range, maintaining a running left sum and computing the right sum on the fly, which leads to O(n) time per query and becomes infeasible for large arrays or many queries. By observing that the condition left = right can be rewritten as 2·prefixSum[P‑1] + nums[P] = prefixSum[L‑1] + prefixSum[R], we see that the left side depends only on the index P and the array itself, while the right side is a constant derived from the query bounds. Thus we can precompute an auxiliary array val[P] = 2·prefixSum[P‑1] + nums[P] for all indices. For each query we compute target = prefixSum[L‑1] + prefixSum[R] and then need to find the smallest P in [L,R] such that val[P] == target. This reduces the problem to a range‑constrained equality search, which can be answered in O(log n) per query using binary search on sorted lists of indices for each distinct val. The overall paradigm is a classic “offline preprocessing + online query” pattern that trades a modest O(n) preprocessing cost for fast query resolution.
Interview Questions on This Problem
Q1How would you explain the time complexity of your solution to a hiring manager at a fintech company that processes millions of transactions per day?
I would say the algorithm runs in O(n) time to build prefix sums and the auxiliary val array, and each query is answered in O(log n) time using binary search on pre‑computed index lists. This means even with millions of queries, the total runtime scales linearly with the array size plus a logarithmic factor per query, which is acceptable for high‑throughput systems.
Q2A senior engineer at a high‑growth startup asks: can we avoid the extra O(n) space for the val array?
Yes, we can compute val on the fly during the binary search by using the prefix sums, but that would add an O(1) computation per candidate index. The trade‑off is between a small constant factor in time and the extra memory; in practice the O(n) space is negligible compared to the array itself.
Q3During an interview at a global product company, you’re asked: what would happen if the array contains negative numbers? Does the algorithm still work?
The algorithm remains correct because the derivation of the equality 2·prefixSum[P‑1] + nums[P] = prefixSum[L‑1] + prefixSum[R] does not rely on positivity. However, the binary search on sorted index lists still works because we only compare equality, not ordering of sums.
Examples
Input
[1, 2, 4, 7, 6, 5, 6], [[0, 4]]
Output
0
Explanation: Step-by-step: with input [1, 2, 4, 7, 6, 5, 6] and query [0, 4], we calculate the sum of the left subarray from index 0 to 0-1 (1) and the sum of the right subarray from index 0+1 to 4 (4). Since the sums are equal, we return 0.
Input
[1, 2, 4, 7, 6, 5, 6], [[3, 6]]
Output
3
Explanation: Step-by-step: with input [1, 2, 4, 7, 6, 5, 6] and query [3, 6], we calculate the sum of the left subarray from index 3 to 3-1 (7) and the sum of the right subarray from index 3+1 to 6 (6 + 5 + 6). Since the sums are equal, we return 3.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= queries.length <= 10^5
- 0 <= L <= R < nums.length
Optimal Approach & Strategy
Precompute prefix sums and an auxiliary array val[P] = 2·prefixSum[P‑1] + nums[P]. Build a map from each val to a sorted list of indices. For each query, compute target = prefixSum[L‑1] + prefixSum[R] and binary search the list for the smallest index in [L,R] that equals target, achieving O(log n) per query.
Brute Force Approach
Loop over every index P in the query range, maintain a running left sum, compute the right sum as total minus left minus nums[P], and check equality. This takes O(length of range) time per query.
Code Solutions
function rangeEquilibriumPivot(nums, queries) {
const n = nums.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
return queries.map(([L, R]) => {
for (let p = L; p <= R; p++) {
const leftSum = pref[p] - pref[L];
const rightSum = pref[R + 1] - pref[p];
if (leftSum === rightSum) return p;
}
return -1;
});
}
function rangeEquilibriumPivotFixed(nums, queries) {
const n = nums.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
return queries.map(([L, R]) => {
for (let p = L; p <= R; p++) {
const leftSum = pref[p] - pref[L];
const rightSum = pref[R + 1] - pref[p];
if (leftSum === rightSum) return p;
}
return -1;
}).map((result, index) => result === -1 ? -1 : Math.min(...queries[index].slice(0, result).map(i => pref[i] - pref[0])) === Math.max(...queries[index].slice(result + 1).map(i => pref[i] - pref[0])) ? result : -1);
}#include <vector>
using namespace std;
vector<int> rangeEquilibriumPivot(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<long long> pref(n + 1, 0);
for(int i = 0; i < n; ++i) pref[i+1] = pref[i] + nums[i];
vector<int> results;
for(auto& q : queries) {
int L = q[0], R = q[1], found = -1;
for(int p = L; p <= R; ++p) {
long long leftSum = (p == L) ? 0 : pref[p] - pref[L];
long long rightSum = (p == R) ? 0 : pref[R + 1] - pref[p + 1];
if(leftSum == rightSum) { found = p; break; }
}
results.push_back(found);
}
return results;
}class Solution {
public int[] rangeEquilibriumPivot(int[] nums, int[][] queries) {
int[] results = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0];
int right = queries[i][1];
boolean found = false;
for (int pivot = left; pivot <= right; pivot++) {
int leftSum = 0;
for (int j = left; j < pivot; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int j = pivot + 1; j <= right; j++) {
rightSum += nums[j];
}
if (leftSum == rightSum) {
results[i] = pivot;
found = true;
break;
}
}
if (!found) {
results[i] = -1;
}
}
return results;
}
}def range_equilibrium_pivot(nums, queries):
results = []
for query in queries:
left, right = query
for pivot in range(left, right + 1):
left_sum = sum(nums[left:pivot])
right_sum = sum(nums[pivot + 1:right + 1])
if left_sum == right_sum:
results.append(pivot)
break
else:
results.append(-1)
return resultsfunction rangeEquilibriumPivot(nums, queries) {
const n = nums.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
return queries.map(([L, R]) => {
for (let p = L; p <= R; p++) {
const leftSum = pref[p] - pref[L];
const rightSum = pref[R + 1] - pref[p];
if (leftSum === rightSum) return p;
}
return -1;
});
}
function rangeEquilibriumPivotFixed(nums, queries) {
const n = nums.length;
const pref = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) pref[i + 1] = pref[i] + nums[i];
return queries.map(([L, R]) => {
for (let p = L; p <= R; p++) {
const leftSum = pref[p] - pref[L];
const rightSum = pref[R + 1] - pref[p];
if (leftSum === rightSum) return p;
}
return -1;
}).map((result, index) => result === -1 ? -1 : Math.min(...queries[index].slice(0, result).map(i => pref[i] - pref[0])) === Math.max(...queries[index].slice(result + 1).map(i => pref[i] - pref[0])) ? result : -1);
}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.