# Find Pivot Index
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-pivot-index)
Canonical: https://scaleengineer.com/dsa/problems/find-pivot-index
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [Nvidia](https://scaleengineer.com/companies/nvidia), [PayPal](https://scaleengineer.com/companies/paypal), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Attentive](https://scaleengineer.com/companies/attentive), [Citigroup](https://scaleengineer.com/companies/citigroup)
---
## Problem
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 <= 104`
* `-1000 <= nums[i] <= 1000`
**Note:** This question is the same as 1991:
# Approaches
## Brute Force
This approach iterates through each possible pivot index and, for each one, calculates the sum of elements to its left and the sum of elements to its right by iterating through the respective subarrays. It's straightforward but inefficient.
**Time:** O(n^2) - For each of the `n` elements in the array, we iterate through the array again to calculate the left and right sums. This results in a nested loop structure. · **Space:** O(1) - We only use a few variables to store the sums and loop counters, so the space used is constant.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** Highly inefficient due to repeated calculations.; The time complexity of O(n^2) makes it unsuitable for large arrays.
### Explanation
The core idea is to test every index to see if it's a pivot. For each index `i`, we perform two separate summations. First, we sum all elements from the beginning of the array up to `i-1` to get the `leftSum`. Second, we sum all elements from `i+1` to the end of the array to get the `rightSum`. If `leftSum` equals `rightSum`, we've found our pivot. Since the problem asks for the *leftmost* pivot index, the first one we find is the answer. If we iterate through all indices and don't find a match, it means no pivot index exists, and we return -1.
```java
class Solution {
public int pivotIndex(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int leftSum = 0;
for (int j = 0; j < i; j++) {
leftSum += nums[j];
}
int rightSum = 0;
for (int k = i + 1; k < nums.length; k++) {
rightSum += nums[k];
}
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
}
```
### Algorithm
- Iterate through each index `i` from `0` to `nums.length - 1`.
- For each `i`, initialize `leftSum` and `rightSum` to 0.
- Calculate `leftSum` by iterating from index `j = 0` to `i - 1` and summing up `nums[j]`.
- Calculate `rightSum` by iterating from index `k = i + 1` to `nums.length - 1` and summing up `nums[k]`.
- If `leftSum` is equal to `rightSum`, then `i` is a pivot index. Since we need the leftmost one, we can return `i` immediately.
- If the loop completes without finding any pivot index, return -1.
## Prefix Sum
This method improves upon the brute-force approach by pre-calculating sums. We create an array for prefix sums (sum from the start up to the current index). This allows for O(1) lookup of the left sum for any potential pivot. The right sum can then be deduced from the total sum and the prefix sum at the current index.
**Time:** O(n) - We perform two separate passes through the array: one to build the prefix sum array and another to find the pivot index. This simplifies to O(n). · **Space:** O(n) - We need an extra array of size `n` to store the prefix sums.
**Pros:** Significant improvement in time complexity over the brute-force approach.; The logic is still relatively easy to follow.
**Cons:** Requires extra space proportional to the size of the input array.
### Explanation
To optimize the repeated sum calculations of the brute-force method, we can precompute the sums. We create a `prefixSum` array where `prefixSum[i]` stores the sum of `nums[0]...nums[i]`. With this array, for any index `i`, the left sum is `prefixSum[i-1]` (or 0 if `i=0`). The total sum of the array is `prefixSum[n-1]`. The right sum for index `i` is `totalSum - prefixSum[i]`. We can then iterate through the indices once, check the condition in O(1) time, and return the first match.
```java
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
if (n == 0) return -1;
int[] prefixSum = new int[n];
prefixSum[0] = nums[0];
for (int i = 1; i < n; i++) {
prefixSum[i] = prefixSum[i-1] + nums[i];
}
int totalSum = prefixSum[n-1];
for (int i = 0; i < n; i++) {
int leftSum = (i == 0) ? 0 : prefixSum[i-1];
int rightSum = totalSum - prefixSum[i];
if (leftSum == rightSum) {
return i;
}
}
return -1;
}
}
```
### Algorithm
- Create a `prefixSum` array of the same size as `nums`.
- Fill the `prefixSum` array such that `prefixSum[i]` is the sum of all elements from `nums[0]` to `nums[i]`.
- Calculate the `totalSum` of the array, which is simply `prefixSum[n-1]`.
- Iterate through each index `i` from `0` to `nums.length - 1`.
- For each index `i`, the `leftSum` is `prefixSum[i-1]` (or 0 if `i=0`).
- The `rightSum` can be calculated as `totalSum - prefixSum[i]`.
- If `leftSum` equals `rightSum`, return `i`.
- If the loop finishes, return -1.
## Single Pass with Total Sum
This is the most optimal approach. It first calculates the total sum of the array. Then, it iterates through the array once, maintaining a running sum of elements to the left. The right sum can be deduced at each step using the total sum, the left sum, and the current element's value, avoiding the need for extra space.
**Time:** O(n) - The algorithm involves two passes through the array: one to calculate the total sum and another to find the pivot. This is linear time complexity. · **Space:** O(1) - We only use a couple of variables (`totalSum`, `leftSum`) to store sums, regardless of the input array size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Efficient for large datasets.
**Cons:** Requires two passes over the array, though it's still linear time.
### Explanation
This approach is the most efficient in terms of both time and space. The key insight is that if we know the `totalSum` of the array and the `leftSum` up to a certain index `i`, we can find the `rightSum` without iterating again. The `rightSum` is simply `totalSum - leftSum - nums[i]`.
The algorithm proceeds in two main steps. First, we compute the `totalSum` of all elements in `nums`. Second, we iterate through `nums` from left to right, maintaining a `leftSum` variable, which starts at 0. In each iteration for index `i`, we check if the current `leftSum` is equal to the calculated `rightSum`. If it is, we've found the pivot. After the check, we update `leftSum` by adding `nums[i]` to prepare for the next index.
```java
class Solution {
public int pivotIndex(int[] nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
// The right sum is totalSum - leftSum - nums[i]
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
}
```
### Algorithm
- First, iterate through the array once to calculate the `totalSum` of all its elements.
- Initialize a variable `leftSum` to 0.
- Iterate through the array again with index `i` from `0` to `nums.length - 1`.
- In each iteration, check if the current `leftSum` is equal to the `rightSum`. The `rightSum` can be calculated on the fly as `totalSum - leftSum - nums[i]`.
- If `leftSum == totalSum - leftSum - nums[i]`, we have found the pivot index, so return `i`.
- If the condition is not met, update `leftSum` by adding the current element: `leftSum += nums[i]`.
- If the loop completes without finding a pivot, return -1.
# Solutions
### Java
```java
class Solution {
public
int pivotIndex(int[] nums) {
int left = 0, right = Arrays.stream(nums).sum();
for (int i = 0; i < nums.length; ++i) {
right -= nums[i];
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
}
}
```
### JavaScript
```javascript
/** * @param {number[]} nums * @return {number} */ var pivotIndex = function (
nums,
) {
let left = 0,
right = nums.reduce((a, b) => a + b);
for (let i = 0; i < nums.length; ++i) {
right -= nums[i];
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
};
```
### CPP
```cpp
class Solution {
public:
int pivotIndex(vector &nums) {
int left = 0, right = accumulate(nums.begin(), nums.end(), 0);
for (int i = 0; i < nums.size(); ++i) {
right -= nums[i];
if (left == right) {
return i;
}
left += nums[i];
}
return -1;
}
};
```
### Python
```python
class Solution:
def pivotIndex(self, nums: List[int]) -> int: left, right = 0, sum(nums) for i, x in enumerate(nums): right -= x if left == right: return i left += x return - 1
```