Abstract / Summary

Find an index in an array where the sum of elements to the left equals the sum to the right.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Prefix Sum

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that searches for an index in an integer array where the sum of the elements to the left of the index equals the sum of the elements to the right. The method returns the first such index it encounters, or -1 when no equilibrium point exists. The algorithm proceeds in a single pass, maintaining running totals for the left and right sides of the current position.

Initialization

At the start of the method two accumulator variables are created.

left  = 0
right = sum(nums)

left holds the cumulative sum of elements that have been processed, while right is initialized to the total sum of the entire array. This setup allows the algorithm to adjust the right-hand sum incrementally as it moves through the list, avoiding repeated full-array summations.

Iteration and Balance Check

The core of the solution is a for loop that enumerates the array, exposing both the index i and the element value n.

for i, n in enumerate(nums):
    right -= n
    if left == right:
        return i
    left  += n

Inside the loop the current element is first subtracted from right, thereby converting right into the sum of all elements that lie strictly to the right of the current index. The equality test left == right then determines whether the left and right sums are balanced at this position. If they match, the index is returned immediately. After the check, the element is added to left, preparing the left accumulator for the next iteration.

Edge Cases Handled

When the input list is empty, the initial right sum is zero and the loop body never executes, causing the method to fall through to the final return statement and yield -1. This correctly indicates that no middle index exists.

If the equilibrium point is at the first position (index 0), the algorithm still works because right is reduced by the first element before the equality test, leaving left at zero. The condition left == right can therefore be satisfied on the very first iteration.

Similarly, when the equilibrium point is at the last position, the loop will have subtracted all preceding elements from right, and after processing the penultimate element right will become zero. The final iteration will compare left (which now equals the sum of all earlier elements) with right (zero). Since the definition requires the right side to be empty, the condition will be true only if the left sum is also zero, which matches the intended behavior.

Performance Optimizations

The algorithm achieves efficiency by computing the total sum once, then updating the right-hand sum in constant time for each element. This eliminates the need for nested loops or repeated summations, resulting in a linear traversal of the input. The early return upon finding a matching index prevents unnecessary processing of the remaining elements, which can be significant for large arrays where the equilibrium point appears early.

The use of simple integer arithmetic and direct variable updates ensures minimal overhead, and the method avoids auxiliary data structures, keeping the memory footprint low. The approach leverages Python’s built-in sum function for the initial total, which is implemented in C and thus runs faster than a manual accumulation loop.

Imagine a long line of numbered blocks sitting on a table. The goal is to figure out if there is a special spot in the middle of the line where the sum of all the blocks to the left is exactly the same as the sum of all the blocks to the right.

To solve this, the code starts by pretending all the blocks are on the right side and zero blocks are on the left side. It then walks down the line one block at a time. Each time it steps, it takes the current block off the right side and adds it to the left side. After the move, it checks to see if the weight of the blocks on the left matches the weight of the blocks on the right. If the two sides weigh the same, that spot is the one being searched for. If the whole line is checked and no such spot is found, the code stops looking because that special middle point does not exist in this line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java					TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python	JS	Java			Go	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM						C#
	trung-hn		Python
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality