DEV Community

Harry Alto
Harry Alto

Posted on

Solving Leetcode Problem of Finding Pivot Index

🧠 Understanding the Pivot Index

When given an array of integers, can we find an index where the sum of all elements to its left equals the sum of all elements to its right?

That index is called the pivot index.

The link to the leetcode problem is here for reference: Leetcode 724

🧾 Problem Statement

You're given a list of integers nums. Find the pivot index where:

sum(nums[0:i]) == sum(nums[i+1:])
Enter fullscreen mode Exit fullscreen mode

Return that index, or -1 if no such index exists.

There are three ways to solve the problem

🚧 Approach 1: Brute Force (O(n²))

In this simple approach, we loop through the array and compute the sum of elements on both sides of every index.

🔍 Logic 

def pivot_index_brute_force(nums):
    for i in range(len(nums)):
        left_sum = sum(nums[:i])
        right_sum = sum(nums[i+1:])
        if left_sum == right_sum:
            return i
    return -1
Enter fullscreen mode Exit fullscreen mode

⚠️ Downside

  • Repeated summing → O(n²) time
  • Works, but not scalable

🧮 Approach 2: Prefix and Suffix Arrays (O(n) Time, O(n) Space)

Let’s optimize it by precomputing prefix and suffix sums.

  • prefix[i]: sum of elements before i
  • suffix[i]: sum of elements after i

We then find the index where prefix[i] == suffix[i].

🔍 Logic 

def pivot_index_prefix_suffix(nums):
    n = len(nums)
    prefix = [0] * n
    suffix = [0] * n

    for i in range(1, n):
        prefix[i] = prefix[i - 1] + nums[i - 1]

    for i in range(n - 2, -1, -1):
        suffix[i] = suffix[i + 1] + nums[i + 1]

    for i in range(n):
        if prefix[i] == suffix[i]:
            return i
    return -1
Enter fullscreen mode Exit fullscreen mode

🧠 Intuition

We calculate the cumulative sum from the start to each index (prefix) and from the end to each index (suffix).

At each index i, if the sum of elements before it (prefix[i]) equals the sum of elements after it (suffix[i]), then that index is the pivot.

This avoids recalculating sums on every iteration and gives an efficient solution using two passes.

🧠 Approach 3: Optimized Mathematical Trick (O(n) Time, O(1) Space)

Here’s where the real magic happens! Let’s derive the core insight.

🧠 Intuition

We know:

left_sum + nums[i] + right_sum = total_sum
Enter fullscreen mode Exit fullscreen mode

Since left_sum == right_sum, we substitute:

2 * left_sum + nums[i] = total_sum
Enter fullscreen mode Exit fullscreen mode

So our pivot condition becomes:

if 2 * running_sum + nums[i] == total_sum
Enter fullscreen mode Exit fullscreen mode

Where running_sum is the sum to the left of index i.

🔍 Logic 

def pivot_index_optimized(nums):
    total_sum = sum(nums)
    running_sum = 0

    for i, val in enumerate(nums):
        if 2 * running_sum + val == total_sum:
            return i
        running_sum += val

    return -1
Enter fullscreen mode Exit fullscreen mode

🧪 Example Walkthrough

Input: nums = [1, 7, 3, 6, 5, 6]

Index Left Sum Value Right Sum 2×Left + Val Equals total?
0 0 1 27 1 ❌
1 1 7 20 9 ❌
2 8 3 17 19 ❌
3 11 6 11 ✅ 28 = 28 ✅ Pivot found

✅ Summary Table

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Simple but inefficient
Prefix & Suffix Arrays O(n) O(n) Fast, uses extra memory
Optimized Math O(n) O(1) Fastest and cleanest ✅

🔚 Final Thoughts

This is a classic case of turning a brute-force problem into an elegant, math-powered solution. It's not just about speed — it's about understanding the data flow.

➡ Know the definition

➡ Translate into equations

➡ Optimize with insight

Top comments (0)