DSA sheet · Arrays · Prefix sum pattern

Pivot Index

The last problem of the prefix sum pattern, and a good one to finish on because the idea is so clean. We look for the spot where the numbers on the left add up to the same total as the numbers on the right. The teacher first writes the direct solution (for every index, add up its left side and its right side with two inner loops), notes that it's O(n²) and slow, goes through the four array patterns to see which one fits, and then shows the key trick: if you know the total of the whole array and the sum on the left, the sum on the right is just total − left − the number itself. That turns the whole thing into one loop.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: add up both sides for every index
• Part B · Optimal: total − left − self = right
• Part C · Revision page

Part 0 · Before starting

What is a prefix sum?

A prefix is a piece of the array that starts at index 0. The prefix sum at index i is the total of nums[0] … nums[i]. Each cell is built from the one before it: prefix[i] = prefix[i-1] + nums[i]. We add one new number per cell, never the whole piece again.

Why sum(l..r) = prefix[r] − prefix[l−1]

prefix[r] is the total of 0…r and prefix[l−1] is the total of 0…l−1. Subtract and the shared part disappears, leaving l…r. Example: sum(4..5) = 5 + 6 = 11 = prefix[5] − prefix[3] = 28 − 17 ✓.

The "−1 / empty prefix = 0" trick: for l = 0 there is no prefix[-1]. We treat the empty prefix (nothing taken) as 0. That is exactly what this problem's statement says too: at index 0 the left sum is 0, because nothing is on the left.

Left sum and right sum with prefix sums

For an index i, with total = sum of the whole array (= the last prefix):

• left sum = everything strictly before i = prefix[i-1] (0 when i = 0).
• right sum = everything strictly after i = total − prefix[i] = total − left − nums[i].

nums:     1   7   3  [6]  5   6        total = 28
          \_______/       \___/
          left = 11       right = 28 - 11 - 6 = 11

The four array patterns (the teacher's checklist)

Part A · Brute force: add up both sides for every index

LeetCode 724 (the same as LeetCode 1991, Find the Middle Index)

1The question in simple words

Given an integer array nums, find the pivot index: an index where the sum of all numbers strictly to its left equals the sum of all numbers strictly to its right. The number at the pivot itself is not part of either side.

• If the index is at the left edge (index 0), its left sum is 0 (nothing there). Same for the right edge: right sum 0.
• If several indexes work, return the leftmost one.
• If none works, return −1.

The teacher checks two spots. At index 2 (the 3): left = 1 + 7 = 8, right = 6 + 5 + 6 = 17. Not equal → not a pivot. At index 3 (the 6): left = 1 + 7 + 3 = 11, right = 5 + 6 = 11. Equal → pivot index 3.

Two more cases from LeetCode: [1, 2, 3] → −1 (no index balances). [2, 1, -1] → 0: left of index 0 is empty (0), right is 1 + (−1) = 0.

2What the constraints tell us

• 1 <= nums.length <= 10⁴ → at least one number. An O(n²) solution is about 10⁸ steps. That is right at the edge: it may pass, but it will be very slow. So we try brute force first, then improve it.
• -1000 <= nums[i] <= 1000 → numbers can be negative. The teacher points this out on purpose: it decides which pattern we can use in Part B.
• Sums are at most 10⁴ × 1000 = 10⁷ in size → a normal int is enough.

3Intuition

Do exactly what the definition says. Stand on each index in turn. Add up everything on its left, add up everything on its right, compare. The first index where they match is the answer.

4Building the logic from examples

• Outer loop: index i from 0 to n − 1. We must try every index, including both edges.
• Left sum: a loop j from 0 while j < i (i.e. up to i − 1), adding nums[j].
• Right sum: a loop k from i + 1 to n − 1, adding nums[k].
• If they're equal → return i right away. Because we go from left to right, the first match is automatically the leftmost one.
• After the outer loop → return −1.

5Approach steps

1. For each i from 0 to n − 1:
2. left = 0; add nums[j] for j = 0 … i − 1.
3. right = 0; add nums[k] for k = i + 1 … n − 1.
4. If left == right → return i.
5. After the loop → return −1.

6Code (Python)

class Solution:
    def pivotIndex(self, nums):
        n = len(nums)
        for i in range(n):
            left = 0
            for j in range(0, i):           # strictly left of i: 0 .. i-1
                left += nums[j]
            right = 0
            for k in range(i + 1, n):       # strictly right of i: i+1 .. n-1
                right += nums[k]
            if left == right:
                return i                    # first match = leftmost pivot
        return -1

7Code line by line

8Dry run (hand table)

nums = [1, 7, 3, 6, 5, 6].

Notice the waste: for i = 3 we re-added 1 + 7 + 3 even though we had 1 + 7 a moment ago. Part B stops doing that.

9Complexity & remember

• Time O(n²). For each i, the two inner loops together touch n − 1 numbers (one covers the left half, the other the right half). That's only n − 1 per index, but it happens inside the outer loop, n times → about n². With n = 10⁴ that's 10⁸: it runs, but it is very slow on LeetCode.
• Space O(1).

Part B · Optimal: total − left − self = right

1The question

Same question. Goal: one pass, O(n).

2Constraints → which pattern?

The teacher runs through the four patterns again, using the constraint that numbers can be negative:

• Two pointers ✗: the array is not sorted, and we need whole sums, not two numbers.
• Sliding window ✗: it needs all numbers positive. With negatives, adding a number can make the sum smaller, so the window doesn't know whether to grow or shrink.
• Kadane's ✗: it gives the maximum subarray sum. We're not looking for a maximum.
• Prefix sum ✓: it's about sums, and negatives are no problem. That's the only one left.

3Intuition

Think of the array as three parts around index i: left | nums[i] | right. Together they make the total. So if we know the total once, and keep a running left sum as we walk, the right sum costs nothing:

  total = 28
  |<------ left = 11 ------>|<nums[3]=6>|<-- right = ? -->|
       1      7      3            6          5      6
                                  right = 28 - 11 - 6 = 11

4Building the logic from examples

Step 1: get the total once

One loop over the array: for [1, 7, 3, 6, 5, 6], total = 28. (In Python just sum(nums); the teacher writes a for-each loop that adds every number.)

Step 2: walk with a running left sum

Start left = 0: when standing on index 0, nothing is on the left. Then at each index:

1. Compute right = total − left − nums[i]. We subtract nums[i] because the current number belongs to neither side.
2. If left == right → return i.
3. Otherwise add nums[i] to left, because when we step to i + 1, the number we're standing on now becomes part of its left side.

5Approach steps

1. total = sum of all numbers.
2. left = 0.
3. For each i: right = total - left - nums[i].
4. If left == right → return i.
5. left += nums[i].
6. After the loop → return −1.

6Code (Python)

class Solution:
    def pivotIndex(self, nums):
        total = 0
        for num in nums:                    # total of the whole array
            total += num

        left = 0                            # nothing on the left of index 0
        for i in range(len(nums)):
            right = total - left - nums[i]  # everything after i
            if left == right:
                return i                    # leftmost pivot
            left += nums[i]                 # nums[i] joins the left side for i+1
        return -1

class Solution:
    def pivotIndex(self, nums):
        n = len(nums)
        prefix = [0] * (n + 1)              # prefix[i] = sum of nums[0..i-1]; prefix[0] = 0 (empty)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        total = prefix[n]
        for i in range(n):
            left = prefix[i]                # sum of 0 .. i-1
            right = total - prefix[i + 1]   # sum of i+1 .. n-1
            if left == right:
                return i
        return -1

The second version shifts the prefix array by one cell so that prefix[0] = 0 is the empty prefix. It uses O(n) extra space for no gain, which is why the teacher keeps just a variable.

7Code line by line

8Dry run (hand table)

nums = [1, 7, 3, 6, 5, 6], total = 28.

Same rows as the brute force table, but each right sum came from one subtraction instead of a loop.

A case with a negative number: [2, 1, -1], total = 2. i = 0: left 0, right = 2 − 0 − 2 = 0 → equal → return 0. Negatives cause no trouble.

No pivot: [1, 2, 3], total = 6. i = 0: right 5 vs left 0. i = 1: left 1, right 3. i = 2: left 3, right 0. Never equal → −1.

9Complexity & remember

• Time O(n): one loop for the total, one loop for the check (each step is O(1)). n + n is still O(n). The teacher's submission was among the fastest.
• Space O(1): just total, left and right.

Part C · Revision page

s = Solution()
print(s.pivotIndex([1, 7, 3, 6, 5, 6]))   # 3
print(s.pivotIndex([1, 2, 3]))            # -1
print(s.pivotIndex([2, 1, -1]))           # 0
print(s.pivotIndex([5]))                  # 0  (both sides empty)
print(s.pivotIndex([0, 0, 0]))            # 0  (leftmost)
print(s.pivotIndex([-1, -1, 0, 1, 1, 0])) # 5

Based on this video: Find Pivot Index | Prefix Sum pattern