JuniorCodeCommonNot answered yet
Equilibrium index where left sum equals right sum
Find an index i of an integer array such that the sum of elements strictly to the left of i equals the sum of elements strictly to the right. Values may be negative; if no such index exists, return -1.
Requirements:
- O(n) time, O(1) extra space — no nested loops, no prefix-sum array.
int equilibriumIndex(const std::vector<int>& a) {
// your code here
}Write the implementation.
First compute the total sum. Then sweep once keeping a running left sum; at index i the right sum is total - left - a[i]. When left == total - left - a[i], return i. One pass after the total, O(n) time and O(1) extra space. Return -1 if none matches.
- ✗Recomputing the right sum from scratch at every index, making it O(n²)
- ✗Forgetting that
a[i]itself belongs to neither side, mis-deriving the right sum - ✗Not handling the empty array or returning a wrong sentinel when no index balances
- →Why does subtracting
a[i]from the total give exactly the right-side sum? - →How would you find all equilibrium indices instead of the first one?
Contents
Task
Find an index where the left sum equals the right sum (values may be negative) in O(n) time and O(1) space; otherwise -1.
Solution
int equilibriumIndex(const std::vector<int>& a) {
long long total = std::accumulate(a.begin(), a.end(), 0LL);
long long left = 0;
for (int i = 0; i < static_cast<int>(a.size()); ++i) {
long long right = total - left - a[i]; // a[i] is on neither side
if (left == right) return i;
left += a[i];
}
return -1;
}Key points
- The right sum is derived from the total:
right = total - left - a[i], no second pass. a[i]is excluded from both sides — forgetting this subtraction is the common bug.- O(n) time, O(1) space;
long longguards against sum overflow.
Contents
