DATA STRUCTURES • ALGORITHMS

Equilibrium Index

An equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes.

Time

O(N)

Space

O(1)

Key Principle 1

Calculate total sum first

Key Principle 2

Track left sum while iterating

Key Principle 3

Right sum = total - left - current

Key Principle 4

Efficient linear scan approach

EQUILIBRIUM_LAB
Current Step
Calculate total sum of array: 28. Initialize left sum = 0.
Playback
Sum Monitor ⠿
Left Sum
0
Right Sum
28
NO MATCH
Scanning Logic ⠿
1int total = sum(nums);
2int left = 0;
3for (int i = 0; i < n; i++) {
4    int right = total - left - nums[i];
5    if (left == right) return i;
6    left += nums[i];
7}
8return -1;
1
[0]
7
[1]
3
[2]
6
[3]
5
[4]
6
[5]
Σ Left
0
!=
Σ Right
28

Loading Lab...