# CSPT21 Lecture 4
## [pivotIndex](https://leetcode.com/problems/find-pivot-index/)

class Solution:
    """
    Understand
    [1,7,3,6,5,6] --> 3
    [1,2,3] --> -1
    [] --> -1
    
    Plan
    Approach 1:
    For each index, see if it's the pivot index by summing all elements
    to the left and right and seeing if they're equal
    Runtime: O(n^2)
    Space: O(1)
    
    Approach 2:
    Keep track of leftSum and rightSum as you iterate left to right in the list.
    Add the previous element to left sum, subtract the current element from rightSum
    When leftSum == rightSum then you're at the pivot index
    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
    
    def pivotIndexApproach1(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
    
    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

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

class Solution:
    """
    Understand
    [1,2,3] --> [1,2,4]
    [9,9] --> [1,0,0]
    [0] --> [1]
    Runtime: O(n)
    Space: O(1)

    """
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1
        i = len(digits) - 1
        while i >= 0:
            currSum = digits[i] + carry
            carry = currSum // 10
            digits[i] = currSum % 10
            i -= 1
        if carry > 0:
            digits.insert(0, carry)
        return digits