Day-13 Find Pivot Index

Background

This problem statement is a part of Leetcode's learning card Arrays and Strings. Under the sub-heading Introduction to Array.

Problem Statement

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

1. The length of nums will be in the range [0, 10000].
2. Each element nums[i] will be an integer in the range [-1000, 1000].

Solution Approach 1

1. Reading the problem statement intuitive method that struck was to slice the list. And keep calculating the sum of those sliced sub-lists. When sum of the elements to the left-hand side of the element and right-hand side of the element matches. Return the index.

Problems with Approach 1

1. This would result in an unoptimized solution. Slicing has its own time complexity depending on the length of the sublist. Overall complexity would have become quadratic.

Solution Approach 2

1. Take a pen and paper and mathematically try observing the pattern.
2. Calculate the total of all elements present in the list.
3. Then compute the sum of all elements to the left-hand side of the current index. Store this sum for each element in a new list.
4. Sum of right-hand side would be. right_hand_side = Total - value of element at current index - sum of left hand side elements at same index.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = 0
        result = -1
        for x in range(0, len(nums)):
            total += nums[x]

        element_sum = 0
        left_side_sum = [0] # Sum of elements to the left of value
        for i in range(1, len(nums)):
            element_sum += nums[i-1]
            left_side_sum.append(element_sum)

        for index in range(0, len(nums)):
            right_side_sum = total - nums[index] - left_side_sum[index]
            if right_side_sum == left_side_sum[index]:
                result = index
                break

        return result

Learnings and Takeaways

1. Time complexity - O(n), Space complexity - O(n)
2. Time complexity of append - O(1)
3. The first element of left_side_sum is initialized to 0 because there is no value to the left-hand side of leftmost element present in the list.