Range Equilibrium Pivot — Problem Statement & Solution Guide
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.
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 the prefix sum array to calculate any subarray sum in O(1) time. For each query, iterate through all P from L to R and verify the equality condition using the precomputed sums, resulting in a time complexity of O(Q * (R-L+1)).
Brute Force Approach
For each query, iterate through every possible pivot index P from L to R. For each P, calculate the sum of elements from L to P-1 and P+1 to R by iterating through those sub-segments, and check if they are equal.
Verified 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.