Equilibrium Balancing Index — Problem Statement & Solution Guide
Problem Description
You are given an array of integers nums, find the leftmost index where the sum of all elements to the left is strictly equal to the sum of all elements to the right. If no such index exists, return -1.
Examples
Input
[1, 2, 3, 4, 5]
Output
3
Explanation: Step-by-step: with input [1, 2, 3, 4, 5], we calculate the sum of all elements to the left (1 + 2 + 3 = 6) and the sum of all elements to the right (4 + 5 = 9). Since 6 is not equal to 9, we move to the next index. At index 3, the sum of all elements to the left (1 + 2 + 3 = 6) is equal to the sum of all elements to the right (4). Therefore, the output is 3.
Input
[10, 20, 30, 40, 50]
Output
0
Explanation: Step-by-step: with input [10, 20, 30, 40, 50], we calculate the sum of all elements to the left (10 + 20 + 30 = 60) and the sum of all elements to the right (40 + 50 = 90). Since 60 is not equal to 90, we move to the next index. At index 0, the sum of all elements to the left (10) is not equal to the sum of all elements to the right (40 + 50 = 90). Therefore, the output is 0.
Constraints
- 1 <= length of `nums` <= 10^5
- -10^5 <= element in `nums` <= 10^5
- At least one element in `nums` is non-zero
Optimal Approach & Strategy
An optimized approach would be to calculate the total sum of the array first and then iterate over the array, keeping track of the sum of elements to the left. This way, we can find the desired index in a single pass. The time complexity of this approach is O(n), where n is the number of elements in the array.
Brute Force Approach
The brute force approach involves iterating over each element in the array, calculating the sum of all elements to the left and the sum of all elements to the right, and checking if they are equal. This approach would have a high time complexity due to the repeated calculations. It is not efficient for large arrays.
Verified Code Solutions
function equilibriumBalanceIndex(nums) {
let leftSum = 0;
let rightSum = nums.reduce((a, b) => a + b, 0);
for (let i = 0; i < nums.length; i++) {
rightSum -= nums[i];
if (leftSum === rightSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}int equilibriumBalanceIndex(vector<int>& nums) {
int leftSum = 0;
int rightSum = 0;
for (int num : nums) {
rightSum += num;
}
for (int i = 0; i < nums.size(); i++) {
rightSum -= nums[i];
if (leftSum == rightSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}public int equilibriumBalanceIndex(int[] nums) {
int leftSum = 0;
int rightSum = 0;
for (int num : nums) {
rightSum += num;
}
for (int i = 0; i < nums.length; i++) {
rightSum -= nums[i];
if (leftSum == rightSum) {
return i;
}
leftSum += nums[i];
}
return -1;
}def equilibrium_balance_index(nums):
left_sum = 0
right_sum = sum(nums)
for i in range(len(nums)):
right_sum -= nums[i]
if left_sum == right_sum:
return i
left_sum += nums[i]
return -1function equilibriumBalanceIndex(nums) {
let leftSum = 0;
let rightSum = nums.reduce((a, b) => a + b, 0);
for (let i = 0; i < nums.length; i++) {
rightSum -= nums[i];
if (leftSum === rightSum) {
return i;
}
leftSum += nums[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.