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.
1class Solution {
2 public int pivotIndex(int[] nums) {
3 int totalSum = 0, leftSum = 0;
4 for (int num : nums) totalSum += num;
5 for (int i = 0; i < nums.length; i++) {
6 if (leftSum == totalSum - leftSum - nums[i]) return i;
7 leftSum += nums[i];
8 }
9 return -1;
10 }
11
12 public static void main(String[] args) {
13 Solution sol = new Solution();
14 int[] nums = {1, 7, 3, 6, 5, 6};
15 System.out.println(sol.pivotIndex(nums)); // Output: 3
16 }
17}This Java solution calculates the total sum of elements and uses a left sum to check for the pivot index by comparing it to the right sum calculated on the fly.
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.
1var pivotIndex = function(nums) {
2 let left = 0, right = nums.length - 1;
3 let leftSum = 0, rightSum = 0;
4 while (left <= right) {
5 if (leftSum < rightSum) {
6 leftSum += nums[left++];
7 } else {
8 rightSum += nums[right--];
9 }
10 }
11 return leftSum === rightSum ? left : -1;
12};
13
14let nums = [1, 7, 3, 6, 5, 6];
15console.log(pivotIndex(nums)); // Output may vary by implementationThis JavaScript solution balances cumulative sums from either end with two pointers as they converge.