mediumArraysPattern: Prefix Sum
Range Equilibrium Pivot Solution
Problem Statement
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 `P = L`, the sum of the left subarray is considered to be `0`. If `P = R`, the sum of the right subarray is considered to be `0`. For each query, return the smallest pivot index `P` that satisfies the condition. If no such index exists within the range `[L, R]`, return `-1` for that query.
Examples
Example 1:
Input:nums = [2, 1, 3, 1, 2, 3, 3]
queries = [[0, 4], [2, 6], [1, 3]]
Output:[2, -1, 2]
Explanation: For query [0, 4], the subarray is [2, 1, 3, 1, 2]. If we choose P = 2, the left sum is nums[0] + nums[1] = 3, and the right sum is nums[3] + nums[4] = 3. Since they are equal, the pivot is 2.
For query [2, 6], the subarray is [3, 1, 2, 3, 3]. There is no index P between 2 and 6 where the left and right sum are equal, so we return -1.
For query [1, 3], the subarray is [1, 3, 1]. If we choose P = 2, the left sum is nums[1] = 1, and the right sum is nums[3] = 1. Since they are equal, the pivot is 2.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= queries.length <= 10^5
- 0 <= L <= R < nums.length
Time: O(N + Q * N) Space: O(N)
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)).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def range_equilibrium_pivot(nums, queries):
n = len(nums)
pref = [0] * (n + 1)
for i in range(n):
pref[i+1] = pref[i] + nums[i]
res = []
for L, R in queries:
found = -1
for p in range(L, R + 1):
left_sum = 0 if p == L else pref[p] - pref[L]
right_sum = 0 if p == R else pref[R+1] - pref[p+1]
if left_sum == right_sum:
found = p
break
res.append(found)
return res