Find Pivot Index

LeetCode 724 | Difficulty: Easy

Easy

Problem Description

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return *the leftmost pivot index*. If no such index exists, return -1.

Example 1:

Input: nums = [1,7,3,6,5,6]
Output: 3
Explanation:
The pivot index is 3.
Left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11
Right sum = nums[4] + nums[5] = 5 + 6 = 11

Example 2:

Input: nums = [1,2,3]
Output: -1
Explanation:
There is no index that satisfies the conditions in the problem statement.

Example 3:

Input: nums = [2,1,-1]
Output: 0
Explanation:
The pivot index is 0.
Left sum = 0 (no elements to the left of index 0)
Right sum = nums[1] + nums[2] = 1 + -1 = 0

Constraints:

- `1 <= nums.length <= 10^4`

- `-1000 <= nums[i] <= 1000`

Note: This question is the same as 1991: https://leetcode.com/problems/find-the-middle-index-in-array/

Topics: Array, Prefix Sum

---

Approach

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 148 ms)

Metric	Value
Runtime	148 ms
Memory	N/A
Date	2018-11-04

Solution

public class Solution {
    public int PivotIndex(int[] nums) {
        
    int len = nums.Length;
    if (len < 3) return -1;

    long[] leftSideSum = new long[len];
    long[] rightSideSum = new long[len];
    leftSideSum[0] = nums[0];
    rightSideSum[len - 1] = nums[len-1];

    for (int i = 1; i < len; i++)
    {
        leftSideSum[i] = nums[i] + leftSideSum[i - 1];
    }

    for (int i = len - 2; i >= 0; i--)
    {
        rightSideSum[i] = nums[i] + rightSideSum[i + 1];
    }

    for (int i = 0; i < len; i++)
    {
        if (leftSideSum[i] == rightSideSum[i]) return i;
        else continue;
    }
    return -1;
    }
}

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Create an array sumLeft where sumLeft[i] is the sum of all the numbers to the left of index i.

Hint 2: Create an array sumRight where sumRight[i] is the sum of all the numbers to the right of index i.

Hint 3: For each index i, check if sumLeft[i] equals sumRight[i]. If so, return i. If no such i is found, return -1.