Skip to content

Volume ITechnology

4.0.22 — Leaders and the Equilibrium Index ​

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.

The problem ​

  1. 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.
  2. 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.

1. Leaders ​

The slow way ​

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.

Walk from the right, carrying the maximum ​

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:

xbest beforeleader?best after
2−∞yes2
52yes5
35no5
45no5
175yes17
1617no17

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 nums

print(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.

2. Equilibrium index ​

The slow way ​

For each index, add up the left side and the right side separately. That is O(n) work per index and O(n^2) in total.

One total, one running sum ​

Here is the key observation. If you know the total of the whole array and the sum of the left side, the right side is just what is left over.

\text{right} = \text{total} - \text{left} - \text{nums}[i]

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 -1

print(equilibrium_index([1, 7, 3, 6, 5, 6]))   # → 3
print(equilibrium_index([1, 2, 3]))            # → -1
print(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:

ixleftright = 28 - \text{left} - xequal?
01027no
17120no
23817no
361111yes

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.

The idea underneath: prefix sums ​

The equilibrium trick is one use of a general tool. A prefix sum array stores, at each position, the sum of everything up to that point.

python
def prefix_sums(nums: list[int]) -> list[int]:
    pre = [0]                        # (1)
    for x in nums:
        pre.append(pre[-1] + x)
    return pre

nums = [3, 1, 4, 1, 5, 9]
pre = prefix_sums(nums)
print(pre)                 # → [0, 3, 4, 8, 9, 14, 23]

def range_sum(pre: list[int], i: int, j: int) -> int:
    return pre[j + 1] - pre[i]       # (2)

print(range_sum(pre, 2, 4))   # → 10

(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.

Complexity ​

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.

What the interviewer will push on ​

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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet