# CSPT19 Lecture 3
## [Single Number](https://leetcode.com/problems/single-number/)

class Solution:
    """
    Understand
    nums = [2,2,1]
    output = 1
    
    [1]
    output = 1
    
    Plan
    Use a dictionary to keep track of num occurences per element
    element --> numOccurence
    Iterate through dictionary and output element that 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 element, numOccurence in counts.items():
            if numOccurence == 1:
                return element

## [Two Sum](https://leetcode.com/problems/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 = 0
    output = [0, 3]
    
    Plan
    Approach 1
    Iterate through all possible pairs and output the pair
    that equals to the target
    Runtime: O(n^2)
    Space: O(1)
    
    Approach 2
    Use a dictionary to keep track of an element seen and its indices
    Runtime: O(n), space: O(n)
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return (i, j)
        # d = {}
        # for i, num in enumerate(nums):
        #     if target - num in d:
        #         return (d[target - num], i)
        #     d[num] = i