Find Balance Index — Problem Statement & Solution Guide
Problem Description
You are given an array of integers elements. Find the index where the total sum of elements before it equals the total sum of elements after it. If no such index exists, return -1.
Examples
Input
[1, 2, 3, 4, 5]
Output
-1
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we calculate the prefix sum and suffix sum for each index. For index 0, prefix sum is 0 and suffix sum is 1 + 2 + 3 + 4 + 5 = 15, which are not equal. We repeat this process for all indices and find that no index has equal prefix and suffix sums, so we return -1.
Input
[2, 3, -1, 8, 4]
Output
3
Explanation: Step-by-step: with input [2, 3, -1, 8, 4], we calculate the prefix sum and suffix sum for each index. For index 3, prefix sum is 2 + 3 + (-1) = 4 and suffix sum is 4, which are equal. So, we return index 3.
Constraints
- 1 <= n <= 10^4
- -1000 <= arr[i] <= 1000
Optimal Approach & Strategy
Use a single pass to calculate the total sum and then find the pivot index in O(n) time complexity
Brute Force Approach
Calculate the sum of deliveries before and after each checkpoint
Verified Code Solutions
function solution(nums) {
for (let i = 0; i < nums.length; i++) {
let prefixSum = 0;
let suffixSum = 0;
for (let j = 0; j < i; j++) {
prefixSum += nums[j];
}
for (let j = i + 1; j < nums.length; j++) {
suffixSum += nums[j];
}
if (prefixSum === suffixSum) {
return i;
}
}
return -1;
}class Solution {
public:
int solution(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
int prefixSum = 0;
int suffixSum = 0;
for (int j = 0; j < i; j++) {
prefixSum += nums[j];
}
for (int j = i + 1; j < nums.size(); j++) {
suffixSum += nums[j];
}
if (prefixSum == suffixSum) {
return i;
}
}
return -1;
}
}class Solution {
public int solution(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int prefixSum = 0;
int suffixSum = 0;
for (int j = 0; j < i; j++) {
prefixSum += nums[j];
}
for (int j = i + 1; j < nums.length; j++) {
suffixSum += nums[j];
}
if (prefixSum == suffixSum) {
return i;
}
}
return -1;
}
}def solution(nums):
for i in range(len(nums)):
prefix_sum = sum(nums[:i])
suffix_sum = sum(nums[i+1:])
if prefix_sum == suffix_sum:
return i
return -1function solution(nums) {
for (let i = 0; i < nums.length; i++) {
let prefixSum = 0;
let suffixSum = 0;
for (let j = 0; j < i; j++) {
prefixSum += nums[j];
}
for (let j = i + 1; j < nums.length; j++) {
suffixSum += nums[j];
}
if (prefixSum === suffixSum) {
return i;
}
}
return -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.