# CSPT21 Lecture 7

## [Jewels and Stones](https://leetcode.com/problems/jewels-and-stones/)

from collections import defaultdict

class Solution:
    """
    Understand
    jewels = "aA", stones = "aAAbbbb"
    output = 3
    
    jewels = "z", stones = "ZZ"
    output = 0
    
    jewels = "abc" stones = "z"
    output = 0
    
    Plan
    Approach 1 (brute-force), O(n^2) runtime, O(1) space
    for each stone, look if that stone is in jewels
    
    Approach 2 hash-and-store approach, O(n) runtime, O(n) space
    put jewels in set, iterate through each stone and checked if the stone is in the jewel 
    
    Approach 3 hash-and-store approach
    Store each character in stone character --> numTimesOccurred
    Now go through each character in jewels, get number of characters from dictionary
    Add it all up, then you get the number of jewels
    """
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        charCount = defaultdict(int)
        for stone in stones: # n
            charCount[stone] += 1
        numJewels = 0 # 1
        for jewel in jewels: # n
            if jewel in charCount: # 1
                numJewels += charCount[jewel]
        return numJewels
    
    # Approach 2
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewelSet = set(jewels) # n
        numJewels = 0 # 1
        for stone in stones: # n
            if stone in jewelSet: # 1
                numJewels += 1 # 1
        return numJewels
    
    # Approach 1
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        numJewels = 0 # 1
        for stone in stones: # n
            if stone in jewels: # n
                numJewels += 1 # 1
        return numJewels

## [Smaller Than Number](https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/)

class Solution:
    """
    Understand
    
    input = [8,1,2,2,3]
    output = [4,0,1,1,3]
    
    input = [1,1,1]
    output = [0,0,0]
    
    input = [4,3,2,1]
    output = [3,2,1,0]
    
    input = [1,2,3]
    output = [0,1,2]
    
    Plan
    Brute-force O(n^2) runtime, O(n) space
    For each element in the list, look at the rest of the list and keep track of how many elements are < it.
    Append the results in an array.
    
    Better approach: sorting + store-and-hash
    Runtime: O(nlogn), Space: O(n)
    Sort the input list, then create a dictionary from element --> its index in the sorted list
    Now go through the original list, and get the number of elements < the current element by using the
    dictionary created in the previous step
    """
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sortedNums = sorted(nums) #nlogn
        numMap = {} # maps from number --> other numbers that are smaller than it
        for (i, num) in enumerate(sortedNums): #n
            if num not in numMap:
                numMap[num] = i
        res = []
        for num in nums: #n
            res.append(numMap[num])
        return res