Classic · Easy to Medium · LeetCode 724 (Find Pivot Index), LeetCode 1299 (Replace with Greatest on Right), LeetCode 303 (Range Sum Query)
Both problems on this page have the same slow answer: for every position, scan everything to one side of it. That is O(n^2). And both have the same fix: carry a running value as you walk, so you never scan the same elements twice.
A leader is an element bigger than everything to its right. In [16, 17, 4, 3, 5, 2] the leaders are 17, 5 and 2. The last element is always a leader, because nothing is to its right.
An equilibrium index is a position where the sum of everything to its left equals the sum of everything to its right. In [1, 7, 3, 6, 5, 6] it is index 3. Left: 1 + 7 + 3 = 11. Right: 5 + 6 = 11. The element at the index itself counts on neither side.
For each element, look at everything to its right and check it is bigger than all of them. That is n checks for each of n elements, O(n^2). The waste: the maximum of the right side is recomputed from scratch every time, even though it changes by at most one element per step.
Start at the right end. Keep the largest value seen so far, best. An element is a leader exactly when it is bigger than best. Then update best.
Why walk from the right? "Bigger than everything to the right" needs the maximum of the right side. Walking right to left, that maximum is exactly what you have seen so far.
python
def leaders(nums: list[int]) -> list[int]: out = [] best = float("-inf") # (1) for x in reversed(nums): # (2) if x > best: # (3) out.append(x) best = x return out[::-1] # (4)print(leaders([16, 17, 4, 3, 5, 2])) # → [17, 5, 2]print(leaders([5, 5, 5])) # → [5]
(1) Nothing has been seen yet, so the last element will always pass the test. That makes the last element a leader, as the definition says.
(2) Walk from the last element to the first.
(3) Strictly bigger. In [5, 5, 5] only the last 5 is a leader, since the others are not bigger than the 5 to their right. If the problem says "greater than or equal", use >=.
(4) We found leaders from right to left. Reverse to report them in their original order.
Trace on [16, 17, 4, 3, 5, 2], read from the right:
x
best before
leader?
best after
2
−∞
yes
2
5
2
yes
5
3
5
no
5
4
5
no
5
17
5
yes
17
16
17
no
17
A close cousin, LeetCode 1299. Replace each element with the largest element to its right, and the last with -1. It is the same walk. Write best into each position before updating best with the old value.
python
def replace_with_greatest_right(nums: list[int]) -> list[int]: best = -1 for i in range(len(nums) - 1, -1, -1): nums[i], best = best, max(best, nums[i]) # (1) return numsprint(replace_with_greatest_right([17, 18, 5, 4, 6, 1])) # → [18, 6, 6, 6, 1, -1]
(1) Both right-hand values use the old nums[i]. So the position gets the maximum to its right, and best then grows to include the old value.
So compute the total once. Then walk left to right, keeping a running sum of the left side. At each index, work out the right side by subtraction and compare.
python
def equilibrium_index(nums: list[int]) -> int: total = sum(nums) # (1) left = 0 for i, x in enumerate(nums): right = total - left - x # (2) if left == right: return i left += x # (3) return -1print(equilibrium_index([1, 7, 3, 6, 5, 6])) # → 3print(equilibrium_index([1, 2, 3])) # → -1print(equilibrium_index([2, 1, -1])) # → 0
(1) One pass to get the total.
(2) The right side is whatever is not on the left and is not this element.
(3) Add this element to the left side after the check. The element at index i belongs to neither side when we test index i. It joins the left side for the next index. Doing this step before the check is the most common bug.
Trace on [1, 7, 3, 6, 5, 6], where the total is 28:
i
x
left
right = 28 - \text{left} - x
equal?
0
1
0
27
no
1
7
1
20
no
2
3
8
17
no
3
6
11
11
yes
The third example, [2, 1, -1], answers 0. The left side of index 0 is empty, so its sum is 0. The right side is 1 + (-1) = 0. An empty side counts as 0, and the code handles that with no special case.
What if the numbers can be negative? The method still works, because it never assumes sums only grow. That is a reason to prefer it over two pointers squeezing in from both ends, which can fail with negatives.
(1) Start with 0, the sum of no elements. Then pre[k] is the sum of the first k elements. This extra 0 removes every special case for ranges that start at index 0.
(2) The sum from index i to j, both included, is the sum of the first j + 1 elements minus the sum of the first i. For indexes 2 to 4: 14 - 4 = 10, which is 4 + 1 + 5.
Building the prefix array costs O(n) once. After that, any range sum costs O(1), one subtraction. If you are asked a thousand range-sum questions about the same array, that is the difference between O(1000 \times n) and O(n + 1000). Chapter 4.4.0 builds on this, adding a hash map to count subarrays with a given sum.
Leaders: O(n) time, one pass from the right. Equilibrium index: O(n) time, two passes, O(1) extra memory. Prefix sums: O(n) to build, then O(1) per range question.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Why do you scan from the right to find leaders?" A leader must be bigger than everything to its right. Scanning from the right, you already hold the biggest value on that side. So each check takes one comparison.
"Find the equilibrium index without extra memory." Add up the whole list once. Then walk left to right with a running left sum. The right sum is the total, minus the left sum, minus the current element.
"When do you add the current element to the left sum?" After the check. The element at the current index belongs to neither side during its own check.
"Answer many range-sum questions fast." Build a prefix-sum list once. Then any range sum is one subtraction: pre[j + 1] - pre[i].
One thing to volunteer: "Both problems replace an inner loop with a value that I carry along. That turns O(n^2) into O(n)."
Next:4.0.23 Matrix Basics. Transpose, add and multiply a matrix with nested loops, and what row-by-column really means.