mediumArraysPattern: Prefix Sum
Equilibrium Balancing Index Solution
Problem Statement
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
Example 1:
Input:[-7, 1, 5, 2, -4, 3, 0]
Output:3
Explanation: Left sum at index 3 is -3 and right sum at index 3 is -3.
Example 2:
Input:[1, 2]
Output:-1
Explanation: No such index exists.
Constraints
- 1 <= length of `nums` <= 10^5
- -10^5 <= element in `nums` <= 10^5
- At least one element in `nums` is non-zero
Time: O(n) Space: O(1)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def find_equilibrium_index(arr):
for i in range(len(arr)):
left_sum = sum(arr[:i])
right_sum = sum(arr[i+1:])
if left_sum == right_sum:
return i
return -1
input_nums = []
for line in sys.stdin:
input_nums.extend(map(int, line.split()))
print(find_equilibrium_index(input_nums))