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/
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.
In this C solution, we first calculate the total sum of the array. We then iterate through the array, comparing the left sum to totalSum - leftSum - nums[i] at each index to determine if it's the pivot point.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the number of elements in the array. We traverse the array twice (once for total sum and once for left sums).
Space Complexity: O(1) as no extra space is used beyond auxiliary variables.
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.
This solution attempts to find the pivot using two pointers from either end of the array, balancing their cumulative sums until they converge.
C++
Java
Python
C#
JavaScript
Time Complexity: Worst case O(n) as each element gets accessed once by either pointer.
Space Complexity: O(1) with additional variables for maintaining the sums and pointers.
| Approach | Complexity |
|---|---|
| Prefix Sum Approach | Time Complexity: O(n) where n is the number of elements in the array. We traverse the array twice (once for total sum and once for left sums). Space Complexity: O(1) as no extra space is used beyond auxiliary variables. |
| Two-Pointer Approach | Time Complexity: Worst case O(n) as each element gets accessed once by either pointer. Space Complexity: O(1) with additional variables for maintaining the sums and pointers. |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,132 views views
Watch 9 more video solutions →Practice Find Pivot Index with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor