Leetcode 724. Find Pivot Index
Problem Explanation
We are given a list of integers and we are required to find an index in this array that partitions the array in such a way that sum of elements in the left partition is equal to the sum of elements in the right partition. The index itself is not part of either partition.
The pivot index is defined as the index where the sum of all numbers to the left of the index is equal to the sum of all numbers to the right of the index. If more than one pivot index exists, we should return the left-most pivot index. If no pivot exists, return -1.
We first compute the sum of all the integers in the given array. This will be the total sum of all elements. Now we iterate through the array, at each step, we add the current number to a variable prefix, which represents the total sum of all numbers to the left of the current index. On each iteration, we also check if the remaining sum, which is total_sum - prefix - current_number, is equal to prefix. If this condition is true, we have found a pivot point and we immediately return the index.
Solution
Python
1 2Python 3class Solution: 4 def pivotIndex(self, nums): 5 total_sum = sum(nums) 6 prefix = 0 7 for i, num in enumerate(nums): 8 if prefix == total_sum - prefix - num: 9 return i 10 prefix += num 11 return -1
Java
1 2Java 3class Solution { 4 public int pivotIndex(int[] nums) { 5 int total_sum = 0, prefix = 0; 6 for (int num : nums) total_sum += num; 7 for (int i = 0; i < nums.length; i++) { 8 if (prefix == total_sum - prefix - nums[i]) 9 return i; 10 prefix += nums[i]; 11 } 12 return -1; 13 } 14}
JavaScript
1 2JavaScript 3const pivotIndex = (nums) => { 4 const total_sum = nums.reduce((a, b) => a + b, 0); 5 let prefix = 0; 6 for (let i = 0; i < nums.length; i++) { 7 if (prefix === (total_sum - prefix - nums[i])) { 8 return i; 9 } 10 prefix += nums[i]; 11 } 12 return -1; 13};
C++
1 2C++ 3class Solution { 4public: 5 int pivotIndex(vector<int>& nums) { 6 int total_sum = accumulate(nums.begin(), nums.end(), 0); 7 int prefix = 0; 8 for (int i = 0; i < nums.size(); i++) { 9 if (prefix == (total_sum - prefix - nums[i])) 10 return i; 11 prefix += nums[i]; 12 } 13 return -1; 14 } 15};
C#
1 2C# 3public class Solution { 4 public int PivotIndex(int[] nums) { 5 int total_sum = nums.Sum(); 6 int prefix = 0; 7 for (int i = 0; i < nums.Length; i++) { 8 if (prefix == total_sum - prefix - nums[i]) 9 return i; 10 prefix += nums[i]; 11 } 12 return -1; 13 } 14}
Walk-through Example
Let's walk through example [1,7,3,6,5,6]
step by step.
-
Mainly we are checking if the sum of left side of current index equals sum of right side of the same index, while iterating our array starting from 0 to end.
-
First, total sum of array is calculated, which is
28
. -
After that we check if the sum of left side equals the sum of right side for each index. Those sums are calculated dynamically during each iteration.
-
For index
0
, left sum is0
and right sum is27
. They are not equal so we continue to next index. -
For index
1
, left sum is1
and right sum is20
. Not equal, continue. -
For index
2
, left sum is8
and right sum is17
. Not equal, continue. -
For index
3
, left sum is11
and right sum is11
. They are equal, so we return index3
as our pivot index. -
If no pivot index were found , we will return
-1
.# Optimization
Above solutions are already optimal, providing a time complexity of O(n)
where n is the length of the list of integers. It does so by performing a single pass over the list rather than checking sums of every possible partition, which would require a double-pass, and thus be less efficient. The algorithm also requires only O(1)
additional space.
Time and Space Complexity
The time complexity of the algorithm is O(n)
, where n
is the length of the array. This is because the algorithm must iterate over the array exactly once, performing constant time operations on each iteration.
The space complexity of the algorithm is O(1)
. It uses only a constant amount of space to store the total sum, prefix sum, and the current numerical value.
Conclusion
The problem of finding the pivot index in an array is a common problem in coding interviews. It tests knowledge of array manipulation, prefix sums, and reasoning about optimizing algorithms to run efficiently on large datasets. The optimal solution provided above calculates the total sum of all elements once, and then calculates the prefix sum as it iterates through the elements in the array. This solution is efficient and performs well even for large input datasets.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.