# CSPT25 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
    
    Brute-force
    Traverse the list from left to right
    For each index, check to see if it's the pivot index
    by summing all elements to the left and to the right
    and seeing if they're equal
    Runtime: O(n^2)
    Space: O(1)
    
    Optimal Approach
    Keep track of left sum and right sum
    Add previous element to left sum
    Subtract current element from right sum
    if both are equal, then you are the left most pivot index
    nums = [1,7,3,6*,5,6]
    leftSum = 11
    rightSum = 11
    Runtime: O(n)
    Space: O(1)
    """
    def pivotIndex(self, nums: List[int]) -> int:
        leftSum = 0
        rightSum = sum(nums) # n
        for (i, num) in enumerate(nums): # n
            if i - 1 >= 0:
                leftSum += nums[i - 1]
            rightSum -= num
            if leftSum == rightSum:
                return i
        return -1
    
    def pivotIndexBruteForce(self, nums: List[int]) -> int:
        for (i, num) in enumerate(nums): # O(n)
            leftSum = self.getLeftSum(i, nums)
            rightSum = self.getRightSum(i, nums) # O(n - 1)
            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

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

class Solution:
    """
    digits = [1,2,3]
    output = [1,2,4]
    
    digits = [9]
    output = [1,0]
    
    digits = [0]
    output = [1]
    
    Plan
    Iterate the list backwards and keep track of the carry
    Make sure to check if theyre's a carry at the most significant digit
    and insert it at the front-most spot of the list
    Runtime: O(n)
    Space: O(1)
    """
    def plusOne(self, digits: List[int]) -> List[int]:
        carry = 1
        i = len(digits) - 1
        while i >= 0: # n
            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) # n
        return digits