Find Pivot Index solution and explanation
IBM
Google
TCS
9 more videos on this problem
Find Pivot Index - Leetcode 724 - PythonNeetCode · 8:42 · 74K views
LeetCode Find Pivot Index Solution Explained - JavaNick White · 7:12 · 21K views
Find Pivot Index (LeetCode 724) | Full solution with constant space | Very importantNikhil Lohia · 13:48 · 9K views
[Java] Leetcode 724. Find Pivot Index [Array #1]Eric Programming · 6:54 · 4K views
724 Find Pivot Index LeetCode (Google Interview Question) JavaScriptdev alex · 5:24 · 3K views
Find Pivot Index | Leetcode - 724Algorithms Made Easy · 7:37 · 2K views
Find Pivot Index - LeetCode 724 - Python #leetcode #leetcode75Deepti Talesra · 4:22 · 2K views
Find Pivot index | Leetcode 724 | Leetcode mastery | Array | Pivot Index | dsa interview questionManish Harit · 6:06 · 2K views
Leetcode | 724. Find Pivot Index | Easy | Java SolutionDeveloper Docs · 5:25 · 2K views
Leetcode 724. Find Pivot Index (Python) Full ExplanationCooper Codes · 7:40 · 964 views
The 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: https://leetcode.com/problems/find-the-middle-index-in-array/
Approach overview
Problem Overview: You are given an integer array nums. The pivot index is the position where the sum of elements on the left equals the sum of elements on the right. Return the leftmost such index. If none exists, return -1.
Approach 1: Prefix Sum Approach (O(n) time, O(n) space)
This method explicitly builds prefix sums to quickly compute the sum of elements before any index. Create a prefix array where prefix[i] stores the sum of elements from index 0 to i. For each index i, the left sum is prefix[i-1] and the right sum is prefix[n-1] - prefix[i]. Iterate through the array and compare these two values. The first index where both sums match is the pivot index. The key idea is that prefix sums let you calculate subarray sums in constant time instead of recomputing them repeatedly.
This approach is easy to reason about and useful when you want clear separation between preprocessing and query logic. However, it requires an additional array of size n, which increases space usage. The technique is widely used in problems involving cumulative sums and range queries, especially when working with array data.
Approach 2: Running Sum / Two-Pointer Style Scan (O(n) time, O(1) space)
A more space-efficient solution avoids the extra prefix array. First compute the total sum of the array. Then iterate from left to right while maintaining a running leftSum. At index i, the right side sum equals totalSum - leftSum - nums[i]. If leftSum equals that value, you found the pivot index. Otherwise, add nums[i] to leftSum and continue.
This works because the total sum allows you to derive the right portion dynamically while scanning the array once. Conceptually it behaves like a balanced scan from both sides: the left side grows while the computed right side shrinks. The algorithm performs a single pass and constant extra work per element. It is a classic application of the prefix sum concept combined with a linear scan similar to patterns seen in two pointers problems.
Recommended for interviews: The running-sum version is the expected solution. It achieves O(n) time with O(1) space and demonstrates that you understand how prefix sums eliminate repeated calculations. Mentioning the explicit prefix array first can show your reasoning process, but optimizing it to constant space signals strong problem-solving skills.
Approach 1: Prefix Sum Approach
The idea is to calculate the total sum of the array elements first. Then, we iterate over the array while maintaining a running sum (prefix sum) of the elements. For each element, we can compute the right sum as rightSum = totalSum - leftSum - nums[i]. If the leftSum equals rightSum at any index, that's our pivot index.
This approach optimizes the solution to a single pass after calculating the total sum initially.
class Solution:
def pivotIndex(self, nums):
totalSum = sum(nums)
leftSum = 0
for i, num in enumerate(nums):
if leftSum == (totalSum - leftSum - num):
return i
leftSum += num
return -1
sol = Solution()
nums = [1, 7, 3, 6, 5, 6]
print(sol.pivotIndex(nums)) # Output: 3class Solution {
public int pivotIndex(int[] nums) {
int totalSum = 0, leftSum = 0;
for (int num : nums) totalSum += num;
for (int i = 0; i < nums.length; i++) {
if (leftSum == totalSum - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 7, 3, 6, 5, 6};
System.out.println(sol.pivotIndex(nums)); // Output: 3
}
}#include <vector>
#include <iostream>
int pivotIndex(std::vector<int>& nums) {
int totalSum = 0, leftSum = 0;
for (int num : nums) totalSum += num;
for (int i = 0; i < nums.size(); ++i) {
if (leftSum == totalSum - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
int main() {
std::vector<int> nums = {1, 7, 3, 6, 5, 6};
std::cout << pivotIndex(nums) << std::endl; // Output: 3
return 0;
}var pivotIndex = function(nums) {
let totalSum = nums.reduce((a, b) => a + b, 0);
let leftSum = 0;
for (let i = 0; i < nums.length; i++) {
if (leftSum === totalSum - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
};
let nums = [1, 7, 3, 6, 5, 6];
console.log(pivotIndex(nums)); // Output: 3#include <stdio.h>
int pivotIndex(int* nums, int numsSize) {
int totalSum = 0, leftSum = 0;
for (int i = 0; i < numsSize; i++) {
totalSum += nums[i];
}
for (int i = 0; i < numsSize; i++) {
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
int main() {
int nums[] = {1, 7, 3, 6, 5, 6};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", pivotIndex(nums, size)); // Output: 3
return 0;
}public class Solution {
public int PivotIndex(int[] nums) {
int totalSum = 0, leftSum = 0;
foreach (int num in nums) totalSum += num;
for (int i = 0; i < nums.Length; i++) {
if (leftSum == totalSum - leftSum - nums[i]) return i;
leftSum += nums[i];
}
return -1;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 7, 3, 6, 5, 6};
Console.WriteLine(sol.PivotIndex(nums)); // Output: 3
}
}This Python solution uses an efficient loop to compare a running left sum to the right sum calculated from the total sum minus the left sum at each index.
Time Complexity: O(n) for a single scan of the array with preliminary total sum computation.
Space Complexity: O(1) as no additional data storage beyond basic variables is needed.
Approach 2: Two-Pointer Approach
This method employs two pointers, one starting from the beginning and another from the end of the array. Both pointers attempt to reach a common point that becomes the pivot index. The trick is to equalize the progressive sums they each encounter by advancing the pointer pointing to the smaller running sum.
class Solution:
def pivotIndex(self, nums):
left, right = 0, len(nums) - 1
leftSum, rightSum = 0, 0
while left <= right:
if leftSum < rightSum:
leftSum += nums[left]
left += 1
else:
rightSum += nums[right]
right -= 1
return left if leftSum == rightSum else -1
sol = Solution()
nums = [1, 7, 3, 6, 5, 6]
print(sol.pivotIndex(nums)) # Output may vary by implementationclass Solution {
public int pivotIndex(int[] nums) {
int left = 0, right = nums.length - 1;
int leftSum = 0, rightSum = 0;
while (left <= right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else {
rightSum += nums[right--];
}
}
return leftSum == rightSum ? left : -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 7, 3, 6, 5, 6};
System.out.println(sol.pivotIndex(nums)); // Output may vary by implementation
}
}#include <vector>
#include <iostream>
int pivotIndex(std::vector<int>& nums) {
int left = 0, right = nums.size() - 1;
int leftSum = 0, rightSum = 0;
while (left <= right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else {
rightSum += nums[right--];
}
}
return leftSum == rightSum ? left : -1;
}
int main() {
std::vector<int> nums = {1, 7, 3, 6, 5, 6};
std::cout << pivotIndex(nums) << std::endl; // Output may vary by implementation
return 0;
}var pivotIndex = function(nums) {
let left = 0, right = nums.length - 1;
let leftSum = 0, rightSum = 0;
while (left <= right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else {
rightSum += nums[right--];
}
}
return leftSum === rightSum ? left : -1;
};
let nums = [1, 7, 3, 6, 5, 6];
console.log(pivotIndex(nums)); // Output may vary by implementation#include <stdio.h>
int pivotIndex(int* nums, int numsSize) {
int left = 0, right = numsSize - 1;
int leftSum = 0, rightSum = 0;
while (left <= right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else {
rightSum += nums[right--];
}
}
return leftSum == rightSum ? left : -1;
}
int main() {
int nums[] = {1, 7, 3, 6, 5, 6};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", pivotIndex(nums, size)); // Output may vary by implementation
return 0;
}public class Solution {
public int PivotIndex(int[] nums) {
int left = 0, right = nums.Length - 1;
int leftSum = 0, rightSum = 0;
while (left <= right) {
if (leftSum < rightSum) {
leftSum += nums[left++];
} else {
rightSum += nums[right--];
}
}
return leftSum == rightSum ? left : -1;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 7, 3, 6, 5, 6};
Console.WriteLine(sol.PivotIndex(nums)); // Output may vary by implementation
}
}This Python implementation utilizes two spatially opposite pointers, adjusting until a central, balanced point is discovered.
Time Complexity: O(n), ensuring each element contributes primarily once to a sum.
Space Complexity: O(1), signifying limited auxiliary storage requirements.
Approach 3: Prefix Sum
We define a variable left to represent the sum of elements to the left of index i in the array nums, and a variable right to represent the sum of elements to the right of index i in the array nums. Initially, left = 0, right = sum_{i = 0}^{n - 1} nums[i].
We traverse the array nums. For the current number x being traversed, we update right = right - x. At this point, if left = right, it indicates that the current index i is the middle position, and we can return it directly. Otherwise, we update left = left + x and continue to traverse the next number.
If the middle position is not found by the end of the traversal, return -1.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.
Similar Problems:
function pivotIndex(nums: number[]): number {
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;
}func pivotIndex(nums []int) int {
var left, right int
for _, x := range nums {
right += x
}
for i, x := range nums {
right -= x
if left == right {
return i
}
left += x
}
return -1
}impl Solution {
pub fn pivot_index(nums: Vec<i32>) -> i32 {
let (mut left, mut right): (i32, i32) = (0, nums.iter().sum());
for i in 0..nums.len() {
right -= nums[i];
if left == right {
return i as i32;
}
left += nums[i];
}
-1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) for a single scan of the array with preliminary total sum computation. Space Complexity: O(1) as no additional data storage beyond basic variables is needed. |
| Two-Pointer Approach | Time Complexity: O(n), ensuring each element contributes primarily once to a sum. Space Complexity: O(1), signifying limited auxiliary storage requirements. |
| Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prefix Sum Array | O(n) | O(n) | When clarity matters or when prefix sums will be reused for multiple range queries |
| Running Sum / Two-Pointer Style Scan | O(n) | O(1) | Best general solution; optimal for interviews and large arrays |
Frequently asked questions
Is Find Pivot Index easy or hard?
Find Pivot Index is categorized as an Easy problem. It mainly tests whether you recognize the prefix sum pattern and avoid recomputing sums repeatedly. Once the relationship between total sum, left sum, and right sum is understood, the implementation is straightforward.
Find Pivot Index Python/Java solution
In Python or Java, compute the total sum of the array first, then iterate while tracking a running left sum. At each index check whether leftSum equals totalSum - leftSum - nums[i]. If the condition holds, return the index; otherwise continue scanning. The logic is identical across languages and runs in O(n) time.
How to solve Find Pivot Index in O(n)?
Start by computing the total sum of the array. Traverse the array while maintaining a variable leftSum. For each index i, compute rightSum as totalSum - leftSum - nums[i]. If leftSum equals rightSum, return i. Otherwise update leftSum += nums[i] and continue the scan.
What is the best approach for Find Pivot Index?
The optimal approach uses a running prefix sum with the total array sum. First compute the total sum, then iterate through the array while maintaining a left sum. At each index, the right sum equals totalSum - leftSum - nums[i]. This solution runs in O(n) time and O(1) extra space.
Is Find Pivot Index asked at Google/Amazon/Meta?
Find Pivot Index appears frequently in coding interviews and practice sets because it tests understanding of prefix sums and array traversal. Variations of the problem have appeared in interviews at companies like Amazon and Google, often as part of array or cumulative sum discussions.
What data structure is used in Find Pivot Index?
The problem primarily uses arrays along with the prefix sum technique. No advanced data structures are required. The optimal implementation only tracks a few integer variables such as totalSum and leftSum while iterating through the array.
What is the time complexity of Find Pivot Index?
The optimal algorithm runs in O(n) time because the array is scanned once after computing the total sum. Each index performs constant-time arithmetic to compare left and right sums. Space complexity can be O(1) with a running sum implementation or O(n) if a prefix sum array is stored.