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.
1public class Solution {
2 public int PivotIndex(int[] nums) {
3 int left = 0, right = nums.Length - 1;
4 int leftSum = 0, rightSum = 0;
5 while (left <= right) {
6 if (leftSum < rightSum) {
7 leftSum += nums[left++];
8 } else {
9 rightSum += nums[right--];
10 }
11 }
12 return leftSum == rightSum ? left : -1;
13 }
14 public static void Main() {
15 Solution sol = new Solution();
16 int[] nums = {1, 7, 3, 6, 5, 6};
17 Console.WriteLine(sol.PivotIndex(nums)); // Output may vary by implementation
18 }
19}The C# implementation leverages two pointers flexed from each end, converging towards a potential pivot point contingent on sum parity.