# CSPT27 Lecture 3
## Single Number

class Solution:
    """
    nums = [2,2,3,1,3]
    output = 1
    
    nums = [1]
    output = 1
    
    nums = [] # not possible
    
    Plan
    Use a dictionary to keep track of number occurences
    Go through dictionary and output the number that only occurs once
    
    Runtime: O(n)
    Space: O(n)
    """
    def singleNumber(self, nums: List[int]) -> int:
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num] += 1
        for key, numOccurence in counts.items():
            if numOccurence == 1:
                return key

## Two Sum

class Solution:
    """
    nums = [3,5,2,1]
    target = 5
    output = [0,2]
    
    nums = [2,1]
    target = 3
    output = [0,1]
    
    nums = [1,2,2,1] 
    target = 2
    output = [0,3]
    
    Plan
    Brute-force approach
    For each element, look at all other elements in the list
    to see if the complement is in nums
    Runtime: O(n^2)
    Space: O(1)
    
    Faster runtime, worse space
    Use a dictionary to store the previous elements seen and the index
    where they are located. For the current element, look if its complement
    is in the dictionary, if so then just get the index that is stored as 
    the value
    Runtime: O(n)
    Space: O(n)
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in indices:
                return [indices[complement], i]
            else:
                indices[num] = i
        
    def bruteForceTwoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num in nums:
            complement = target - num
            for j, otherNum in nums:
                if j == i:
                    continue
                elif otherNum == complement:
                    return [i, j]