# CSPT17 Lecture 5
## [Pivot Index](https://leetcode.com/problems/find-pivot-index)

class Solution:
    """
    Understand
    
    [1,7,3,6,5,6] --> 3
    [] --> -1
    [1,2,3] --> -1
    
    Plan
    Keep track of two sums: left sum and right sum
    Right sum is initialized to sum of total list
    Walk the list from left to right
        Keep adding left sum
        Update right sum to subtract the current element
        if left sum == right sum then we've found the pivot index
    return -1
    
    Runtime O(n)
    Space O(1)
    """
    def pivotIndex(self, nums: List[int]) -> int:
        leftSum = 0
        rightSum = sum(nums)
        for (i, num) in enumerate(nums):
            if i - 1 >= 0:
                leftSum += nums[i - 1]
            rightSum -= nums[i]
            if leftSum == rightSum:
                return i
        return -1

## [Add One](https://leetcode.com/problems/plus-one/)

class Solution:
    """
    Understand
    [1,2,3] --> [1,2,4]
    [9,9] --> [1,0,0]
    [2,0,9] --> [2,1,0]
    [0] --> [1]
    
    Plan
    Iterate the list backwards and keep track of the carry
    In each digit we need to update we 
    make sure if there's a carry for the next digit
    Make sure to insert carry at the front of the list if needed
    """
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1
        i = len(digits) - 1
        while i >= 0:
            currSum = digits[i] + carry
            carry = int(currSum / 10)
            currSum = currSum % 10
            digits[i] = currSum
            i -= 1
        if carry > 0:
            digits.insert(0, carry)
        return digits