LeetCode - 724. Find Pivot Index

Thoughts:

I choose prefix sum to solve this problem. And I can find the pivot index by checking the left sum and right sum. The time complexity will be O(n).

Thoughts visuzlization:

origin: [1,7,3,6,5,6]

prefixSums: [1,8,11,17,22,28]

i = 0
left: prefixSums[-1], not exists, so 0
right: prefixSums[length -1] - prefixSums[0]

...

i = 3
left: prefixSums[2]
right: prefixSums[length -1] - prefixSums[3]
left equals right, so return i

Code:

/**
 * @param {number[]} nums
 * @return {number}
 */
var pivotIndex = function (nums) {
  const prefixSums = [];
  let sum = 0;
  for (let num of nums) {
    sum += num;
    prefixSums.push(sum);
  }
  for (let i = 0; i < nums.length; i++) {
    const left = prefixSums[i - 1] || 0;
    const right = prefixSums[nums.length - 1] - prefixSums[i];
    if (left === right) {
      return i;
    }
  }
  return -1;
};

Reference

Original link

Basic prefix sum