Hashmap

def canConstruct(ransomNote: str, magazine: str) -> bool:
    # Build frequency map
    charMap = {}
    for c in magazine:
        if c not in charMap:
            charMap[c] = 0
        charMap[c] += 1

    for c in ransomNote:
        if c not in charMap or charMap[c] == 0:
            return False
        charMap[c] -= 1

    return True

Time: O(n)

Space: O(n)

def isIsomorphic(self, s: str, t: str) -> bool:
    # Use two maps for s -> t and t -> s
    sMap, tMap = {}, {}

    for i in range(len(s)):
        charS, charT = s[i], t[i]
        if charS in sMap and sMap[charS] != charT:
            return False
        if charT in tMap and tMap[charT] != charS:
            return False

        sMap[charS] = charT
        tMap[charT] = charS

    return True

Time: O(n)

Space: O(n)

NOTE: The solution for "Word Pattern" can also be used to solve this problem.

def convertPatternToTuple(string: str) -> tuple:
    # Example: "dog cat cat dog" -> (0, 1, 1, 0)
    def wordsToTuple(words: str) -> tuple:
        m, i, result = {}, 0, []
        words = words.split()

        for word in words:
            if word not in m:
                m[word] = i
                i += 1
            result.append(m[word])

        return tuple(result)

    # Example: "abba" -> (0, 1, 1, 0)
    def patternToTuple(pattern: str) -> tuple:
        m, i, result = {}, 0, []

        for c in pattern:
            if c not in m:
                m[c] = i
                i += 1
            result.append(m[c])

        return tuple(result)

    return patternToTuple(pattern) == wordsToTuple(s)

Time: O(n)

Space: O(n)

Alternative solution:

def convertPatternToTuple(string: str) -> tuple:
    # Use two maps for word -> char and char -> word
    wordMap, charMap = {}, {}
    words = s.split()

    if len(pattern) != len(words):
        return False

    for i in range(len(pattern)):
        char = pattern[i]
        word = words[i]

        if char in charMap and charMap[char] != word:
            return False
        if word in wordMap and wordMap[word] != char:
            return False

        charMap[char] = word
        wordMap[word] = char

    return True

Time: O(n)

Space: O(n)

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False

    m = {}

    for c in s:
        m[c] = m.get(c, 0) + 1

    for c in t:
        if c not in m or m[c] == 0:
            return False
        m[c] -= 1

    return True

Time: O(n)

Space: O(n)

def twoSum(nums: List[int], target: int) -> List[int]:
    m = {}

    for i in range(len(nums)):
        complement = target - nums[i]
        if complement in m:
            return [m[complement], i]
        m[nums[i]] = i

Time: O(n)

Space: O(n)

def isHappy(n: int) -> bool:
    s = set()

    while True:
        total = sum([int(c) * int(c) for c in str(n)])

        if total == 1:
            return True
        if total in s:
            return False

        n = total
        s.add(total)

Time: O(n)

Space: O(n)

Alternative solution:

def isHappy(self, n: int) -> bool:
    def getTotal(n: int) -> int:
        total = 0
        while n > 0:
            digit = n % 10
            total += digit * digit
            n = n // 10
        return total

    slow = fast = n

    while True:
        slow = getTotal(slow)
        fast = getTotal(getTotal(fast))

        if fast == 1:
            return True
        if slow == fast:
            return False

Time: O(n)

Space: O(1)

def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    m = {}

    for i in range(len(nums)):
        if nums[i] in m and i - m[nums[i]] <= k:
            return True
        m[nums[i]] = i

    return False

Time: O(n)

Space: O(n)

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    m = {}

    # Anagrams always result in same sorted string. Use as key
    for word in strs:
        base = "".join(sorted(word))
        if base not in m:
            m[base] = [word]
        else:
            m[base].append(word)

    return list(m.values())

Time: O(n * (k log k)) where n = len(strs), k = max(len(word))

Space: O(n * k)

Alternative solution:

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    m = {}

    # Use char frequency as key
    for word in strs:
        buckets = [0] * 26
        for char in word:
            buckets[ord(char) - 97] += 1

        tup = tuple(buckets)
        if tup not in m:
            m[tup] = [word]
        else:
            m[tup].append(word)

    return list(m.values())

Time: O(n * k)

Space: O(n * k)

def longestConsecutive(nums: List[int]) -> int:
    s = set(nums) # Remove duplicates and have O(1) lookup
    answer = 0

    for num in nums:
        # Only check sequence if num is lowest value (start of new sequence)
        if num - 1 not in s:
            end = num + 1
            while end in s:
                end += 1
            answer = max(answer, end - num)

    return answer

Time: O(n)

Space: O(n)

Alternative solution:

def longestConsecutive(nums: List[int]) -> int:
    nums = set(nums)
    # Key: num
    # Val: length of sequence using num as upper/lower bound
    answer, m = 0, {}

    for num in nums:
        lower = m.get(num - 1, 0)
        upper = m.get(num + 1, 0)

        # Merge intervals
        total = lower + upper + 1
        m[num - lower] = total
        m[num + upper] = total

        answer = max(answer, total)

    return answer

Time: O(n)

Space: O(n)