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

 class Solution:
    """
    Understand
    jewels = "aA", stones = "aAAbbbb"
    
    jewels = "z", stones = "ZZ"
    
    Plan
    Brute-force
    For each stone, check if the stone is in the jewels string
    Keep track of how many stones are jewels
    return that count
    
    Hash-and-store
    Store each jewel in a set, then check if the stone is in that set
    """
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        numJewels = 0
        jewels = set(list(jewels))
        for stone in stones: # O(n)
            if stone in jewels: # O(1)
                numJewels += 1
        return numJewels

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

 class Solution:
    """
    Understand
    nums = [8,1,2,2,3]
    output = [4,0,1,1,3]

    nums = [1,1,1,1]
    output = [0,0,0,0]

    nums = [4,3,2,1]
    output = [3,2,1,0]
    
    nums = [1,2,3]
    output = [0,1,2]
    
    Plan
    Brute-force approach
    for each element, look at all other elements and count how many elements are less than it
    Runtime: O(n^2)
    Space: O(1)
    
    Sort, then store-and-hash
    Sort the input list, create a dictionary where element --> numElements that are smaller than it. The number
    of elements smaller, is the index of the current element (except duplicates).
    Go through original list again, and simply construct the resulting list using the values in the dictionary

    Runtime: O(nlogn)
    Space: O(n)
    """
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sortedNums = sorted(nums) # nlogn
        numMap = {} # map from number --> count of other numbers that are smaller than it
        for (i, num) in enumerate(sortedNums):
            if num not in numMap:
                numMap[num] = i
        res = []
        for num in nums:
            res.append(numMap[num])
        return res