# CSPT23 Lecture 4
## [Find Pivot Index](https://leetcode.com/problems/find-pivot-index/)

class Solution:
    """
    nums = [1,7,3,6,5,6]
    output = 3
    
    nums = [1,2,3]
    output = -1
    
    nums = [1]
    output = 0
    
    nums = [0,0,0]
    output = 0
    
    Plan
    Brute-force O(n^2)
    For each number, check if they're the pivot index by summing
    all the elements to its left and right and checking if they're equal
    
    Optimal Approach O(n)
    Manually keep track of leftSum and rightSum as you go through
    left to right. Add previous element to leftSum, decrease rightSum
    by the current element. The pivot index is when leftSum == rightSum.
    nums = [1,7,3,6*,5,6]
    leftSum = 11
    rightSum = 11
    i = 3
    """
    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 -= num
            if leftSum == rightSum:
                return i
        return -1
        
        
    def bruteForcepivotIndex(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            leftSum = self.getLeftSum(i, nums)
            rightSum = self.getRightSum(i, nums)
            if leftSum == rightSum:
                return i
        return -1

    def getLeftSum(self, i, nums):
        if i == 0:
            return 0
        currSum = 0
        for j in range(i):
            currSum += nums[j]
        return currSum
    
    def getRightSum(self, i, nums):
        if i == len(nums) - 1:
            return 0
        currSum = 0
        for j in range(i + 1, len(nums)):
            currSum += nums[j]
        return currSum

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

class Solution:
    """
    [1,2,3]-->[1,2,4]
    [1,2,9]-->[1,3,0]
    [0]-->[1]
    [9,9]-->[1,0,0]
    Plan
    Start from right most digit and add one
    Keep going to the left if there's a carry
    If there's no carry then you don't need to go through the other left digits
    """
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1
        i = len(digits) - 1
        while i >= 0:
            if carry == 0:
                return digits
            currSum = digits[i] + carry
            carry = currSum // 10
            digits[i] = currSum % 10
            i -= 1
        if carry > 0:
            digits.insert(0, carry)
        return digits