Abstract / Summary

Find the integer in an array where the sum of all numbers to its left equals the sum of all numbers to its 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 84% (300k+ submissions).

Typical patterns to solve this problem:

• Math
• 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 class Solution with a method pivotInteger that receives a positive integer n and returns a pivot integer i such that the sum of all integers from 1 to i equals the sum of all integers from i to n. If no such integer exists, the method returns -1. The algorithm relies on the arithmetic series formula to compute the total sum of the range [1, n] and then iterates backward from n while maintaining two running totals: the cumulative sum of the upper segment and the remaining sum of the lower segment.

Key Steps

Computing the total triangular sum

The first operation calculates the sum of the first n natural numbers using the closed-form expression for a triangular number.

all = n * (n + 1) // 2  # triangle number

This single arithmetic expression replaces an explicit loop, providing an immediate value for the total sum of the interval [1, n].

Initializing the upper segment accumulator

A variable upper is introduced to hold the cumulative sum of the numbers that belong to the upper segment [i, n] as the loop proceeds. It starts at zero because no elements have been added yet.

upper = 0

Backward iteration and simultaneous updates

The core of the algorithm is a reverse for loop that walks from n down to 0. In each iteration the current index i is added to upper, representing the inclusion of i in the upper segment.

for i in range(n, -1, -1):
    upper += i

Immediately after the addition, three conditions are examined:

1. If upper matches the total sum stored in all, the current i is the pivot and is returned.

    if upper == all:
        return i

2. If upper exceeds all, the sums can no longer be equal for any smaller i, so the method returns -1 to indicate the absence of a pivot.

    if upper >  all:
        return -1

3. If neither condition holds, the algorithm subtracts the current i from all. This step effectively reduces the remaining lower-segment sum, keeping all synchronized with the sum of numbers that have not yet been moved to the upper segment.

    all   -= i

By updating all in place, the code avoids recomputing the lower-segment sum from scratch on each iteration.

Edge Cases Handled

When n equals 0, the triangular sum all becomes 0. The loop starts with i = 0, adds 0 to upper, and the equality upper == all holds, causing the method to return 0. This correctly identifies 0 as the pivot for an empty range.

For n = 1, the total sum is 1. The loop first processes i = 1, making upper = 1. The equality condition is satisfied, and the method returns 1, which is the only integer that can serve as a pivot.

If the input n yields no integer that balances the two sums-such as n = 2 where the total sum is 3-the loop will eventually make upper exceed all. At that point the early exit return -1 is triggered, correctly indicating the lack of a pivot.

The early termination when upper surpasses all ensures that the algorithm does not continue scanning values that can no longer satisfy the equality condition, thereby handling the “no solution” scenario efficiently.

Performance Optimizations

The code incorporates several optimizations that reduce computational overhead.

First, the use of the triangular number formula eliminates the need for an O(n) accumulation of the total sum, collapsing that work into a constant-time arithmetic operation.

Second, the reverse iteration combined with the in-place subtraction all -= i maintains a running difference between the two segment sums without allocating additional data structures. This approach avoids repeated summations of sub-ranges, which would otherwise increase the number of arithmetic operations.

Third, the early exit conditions-returning as soon as upper equals all or exceeds it-prevent unnecessary loop iterations once the outcome is determined. This early break reduces the number of steps for inputs where the pivot is found early or where it is impossible to find one, contributing to faster execution for many inputs.

Overall, the algorithm achieves its goal with a single pass over the range [0, n], leveraging arithmetic shortcuts and early termination to keep the runtime minimal while using only a few scalar variables.

Imagine there is a long row of blocks standing in a line, and they are numbered from one all the way up to a big number called n. Think of a magic spot somewhere in that line where all the block numbers before it add up to the exact same total as all the block numbers after it, including the spot itself.

To find this special spot, the computer starts by calculating the total sum of every single block in the row by using a clever little shortcut for adding up a long sequence. Next, the computer starts thinking about the blocks starting from the very end of the line and moving backward toward the beginning. As it goes, it keeps a running total of the blocks it has visited.

With every new step, the computer checks to see if the sum of the blocks it has seen so far equals the total sum of the rest of the line. If the two amounts match, it has found the hidden pivot spot. If the running total ever gets bigger than what is left on the other side, then this magic spot does not exist in this row.

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	Python		Java		C++				TS
	WalkCCC	Python		Java		C++
	leetcode.ca	Python		Java		C++	Go	PHP	Rust	TS
	Progiez	Python		Java		C++
github	chandansgowda	Python
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq					C++
	JoshCrozier		JS
	pruthvikp	Python
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, PHP, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
pruthvikp	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