Equilibrium Index

52.3k
0

Given an integer array nums, return the first index where the sum of all elements on the left equals the sum of all elements on the right.

The element at the equilibrium index is not included in either sum.

Return -1 when no equilibrium index exists.

Example 1

Input: nums = [-7, 1, 5, 2, -4, 3, 0]

Output: 3

Explanation: At index 3, the left side sum is -7 + 1 + 5 = -1, and the right side sum is -4 + 3 + 0 = -1. Both are equal, so index 3 is the equilibrium index.

Example 2

Input: nums = [1, 2, 3]

Output: -1

Explanation: There is no index where the left side sum is equal to the right side sum.

Brute Force Approach

The most direct idea checks every index as a possible equilibrium position.

For each selected index, the complete sum on the left and the complete sum on the right are calculated separately. This follows the definition exactly, but many elements are added repeatedly for different indices.

Algorithm

  • Store the array size in n. If n == 0, return -1 because an empty array contains no valid index.

  • Traverse every index from 0 to n - 1, treating the current position as a possible equilibrium index.

  • Initialize leftSum with 0 and add all elements before the current index, keeping nums[index] excluded from the left side.

  • Initialize rightSum with 0 and add all elements after the current index, again excluding the current element.

  • Compare leftSum and rightSum. Return the current index immediately when both are equal so that the first equilibrium index is returned.

  • Return -1 after every position has been checked without finding equal side sums.

Dry Run

Equilibrium Index Brute Force Dry Run.png

Equilibrium Index Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int equilibriumIndex(vector<int>& nums) {
int n = nums.size();
// No valid index exists in an empty array.
if (n == 0) {
return -1;
}
for (int index = 0; index < n; index++) {
long long leftSum = 0;
long long rightSum = 0;
// Add all elements before the current index.
for (int left = 0; left < index; left++) {
leftSum += nums[left];
}
// Add all elements after the current index.
for (int right = index + 1; right < n; right++) {
rightSum += nums[right];
}
/*
* Equal side sums make the current
* position an equilibrium index.
*/
if (leftSum == rightSum) {
return index;
}
}
return -1;
}
};
int main() {
vector<int> nums = {1, 7, 3, 6, 5, 6};
Solution solution;
cout << solution.equilibriumIndex(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N²), where N represents the array size. Every index may require separate traversals of the elements on the left and right.

Space Complexity: O(1), because only index variables, leftSum, and rightSum require auxiliary storage.

Better Approach

The Brute Force Approach repeatedly recalculates the same left-side and right-side sums.

Two helper arrays can store these sums in advance. After preprocessing, every index requires only one comparison between the already available left and right sums.

Algorithm

  • Store the array size in n. If the array is empty, return -1.

  • Create leftSum and rightSum arrays of size n. Here, leftSum[index] stores the sum of elements before index, while rightSum[index] stores the sum after it.

  • Set leftSum[0] = 0 because no element exists before the first position. For every later index, use leftSum[index - 1] + nums[index - 1] to build the required left-side sum.

  • Set rightSum[n - 1] = 0 because no element exists after the last position. Traverse from right to left and use rightSum[index + 1] + nums[index + 1] to build each right-side sum.

  • Traverse the indices from left to right and compare the corresponding values in leftSum and rightSum. Return the first index where they are equal.

  • Return -1 if no index satisfies the equilibrium condition.

Dry Run

Equilibrium Index Better Approach Dry Run.png

Equilibrium Index Better Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int equilibriumIndex(vector<int>& nums) {
int n = nums.size();
// No valid index exists in an empty array.
if (n == 0) {
return -1;
}
vector<long long> leftSum(n, 0);
vector<long long> rightSum(n, 0);
/*
* Each position stores the sum of
* all elements before that index.
*/
for (int index = 1; index < n; index++) {
leftSum[index] =
leftSum[index - 1] + nums[index - 1];
}
/*
* Each position stores the sum of
* all elements after that index.
*/
for (int index = n - 2; index >= 0; index--) {
rightSum[index] =
rightSum[index + 1] + nums[index + 1];
}
for (int index = 0; index < n; index++) {
/*
* Return immediately so the first
* equilibrium index is selected.
*/
if (leftSum[index] == rightSum[index]) {
return index;
}
}
return -1;
}
};
int main() {
vector<int> nums = {1, 7, 3, 6, 5, 6};
Solution solution;
cout << solution.equilibriumIndex(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. Separate linear traversals build the left sums, build the right sums, and find the first matching index.

Space Complexity: O(N), because two arrays of size N store the left-side and right-side sums.

Optimal Approach

A separate right-side array is unnecessary when the total sum of the array is already known.

At any index, subtracting the current element and the accumulated left-side sum from the total gives the right-side sum immediately. The left-side sum can then be updated while moving forward.

Algorithm

  • Store the array size in n. If n == 0, return -1.

  • Calculate totalSum by adding every array element. Knowing the complete sum allows the right-side sum to be obtained without storing a separate suffix array.

  • Initialize leftSum with 0 because no element exists before index 0.

  • Traverse the array from left to right and calculate rightSum = totalSum - leftSum - nums[index]. Subtracting the current value ensures that it belongs to neither side.

  • If leftSum == rightSum, return the current index immediately. Otherwise, add nums[index] to leftSum so it becomes part of the left side for the next position.

  • Return -1 after the complete traversal if no equilibrium index is found.

Dry Run

Equilibrium Index Optimal Approach Dry Run.png

Equilibrium Index Optimal Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int equilibriumIndex(vector<int>& nums) {
int n = nums.size();
// No valid index exists in an empty array.
if (n == 0) {
return -1;
}
long long totalSum = 0;
// The total sum helps derive the right-side sum.
for (int value : nums) {
totalSum += value;
}
long long leftSum = 0;
for (int index = 0; index < n; index++) {
/*
* Remove the left side and current value
* from the total to get the right side.
*/
long long rightSum =
totalSum - leftSum - nums[index];
// Equal side sums make this an equilibrium index.
if (leftSum == rightSum) {
return index;
}
/*
* The current value joins the left side
* only after its index has been checked.
*/
leftSum += nums[index];
}
return -1;
}
};
int main() {
vector<int> nums = {1, 7, 3, 6, 5, 6};
Solution solution;
cout << solution.equilibriumIndex(nums) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N represents the array size. One traversal calculates totalSum, and another traversal checks every index.

Space Complexity: O(1), because only totalSum, leftSum, and rightSum require auxiliary storage.

FAQs

Q1. Why is the current element excluded from both sums?

The equilibrium condition compares only the elements located before and after the selected index. The value stored at the index belongs to neither side.

Q2. Why does the algorithm return immediately after finding a match?

Immediate return ensures that the first equilibrium index is produced when multiple valid indices exist.

Q3. Why is leftSum updated after the comparison in the Optimal Approach?

At the current index, nums[index] must not belong to the left side. The value becomes part of leftSum only when traversal moves to the next position.

Q4. Can index 0 or index n - 1 be an equilibrium index?

Yes. At index 0, the left sum is 0. At index n - 1, the right sum is 0. Either boundary is valid when the opposite side also sums to 0.

Q5. What happens when the array contains one element?

Index 0 becomes the equilibrium index because both the left-side and right-side sums are 0.

Q6. Can negative numbers appear in the array?

Yes. The condition depends only on equality between the two side sums, so positive, negative, and zero values are handled without any change.

Arrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Output: 10 50 Exp...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0