LeetCode 724 solution

724. Find Pivot Index

#Easy #Cumulative_sum

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

python

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        pivot = 0
        n = len(nums)
        while n >= 0:
            if sum(nums[:pivot]) == sum(nums[pivot+1:]):
                break
            elif n == 1:
                return -1
            else:
                pivot += 1
                n -= 1
        return pivot

First solution for this problem was like this. But the time complexity and space complexity were too high. Because of the repeated sum part and the unnecessary while loop was the problem of my code.

So had to make cumulative sum and efficient loop to get better code. And it looks like this.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        left_sum = 0

        for i, num in enumerate(nums):
            if left_sum == (total_sum - left_sum - num):
                return i
            left_sum += num

        return -1

This code only execute sum once. The complexity of sum operation increase as the array increase. With total sum, the calculating of part sum is much efficient than before. So the time complexity decreased from $O(n^2)$ to $O(n)$.