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.
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.
1#include <stdio.h>
2
3int pivotIndex(int* nums, int numsSize) {
4 int totalSum = 0, leftSum = 0;
5 for (int i = 0; i < numsSize; i++) {
6 totalSum += nums[i];
7 }
8 for (int i = 0; i < numsSize; i++) {
9 if (leftSum == totalSum - leftSum - nums[i]) {
10 return i;
11 }
12 leftSum += nums[i];
13 }
14 return -1;
15}
16
17int main() {
18 int nums[] = {1, 7, 3, 6, 5, 6};
19 int size = sizeof(nums) / sizeof(nums[0]);
20 printf("%d\n", pivotIndex(nums, size)); // Output: 3
21 return 0;
22}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.
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.
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.
1class Solution:
2 def pivotIndex(self, nums):
3 left, right = 0, len(nums) - 1
4 leftSum, rightSum = 0, 0
5 while left <= right:
6 if leftSum < rightSum:
7 leftSum += nums[left]
8 left += 1
9 else:
10 rightSum += nums[right]
11 right -= 1
12 return left if leftSum == rightSum else -1
13
14sol = Solution()
15nums = [1, 7, 3, 6, 5, 6]
16print(sol.pivotIndex(nums)) # Output may vary by implementationThis Python implementation utilizes two spatially opposite pointers, adjusting until a central, balanced point is discovered.