Skip to content

Hashing

Checking for existence

  • With array: Need O(n)
  • With hash map or set: Only need O(1)

1. Two sum

Problem description - Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def two_sum(nums, target):
    hash_map = {}
    for i in range(len(nums)):
        num = nums[i]
        complement = target - num
        if complement in hash_map: # This operation is O(1) for the hash map
            return [i, hash_map[complement]]
        hash_map[num] = i
    return [-1, -1]
    # Time: O(n)
    # Space: O(n) - number of keys of the hash_map scales linearly with input size

2351. First letter to appear twice

Problem description - Easy

Given a string s, return the first character to appear twice. It is guaranteed that the input will have a duplicate character.

1
2
3
4
5
6
7
8
def appear_twice(s):
    seen = set()
    for c in s:
        if c in seen:
            return c
        seen.add(c)
    # Time: O(n)
    # Space: O(1) since number of characters are bounded by 26, constant. Or O(m) with m is number of allowed characters

Example 3 - find numbers

Problem description - Easy

Given an integer array nums, find all the unique numbers x in nums that satisfy the following: x + 1 is not in nums, and x - 1 is not in nums

1
2
3
4
5
6
7
8
9
def find_nums(nums):
    ans = []
    nums = set(nums)
    for num in nums:
        if (num + 1) not in nums and (num - 1) not in nums:
            ans.append(num)
    return ans
    # Time: O(n)
    # Space: O(n)

1832. Check if the Sentence Is Pangram

Problem description - Easy

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, return true if sentence is a pangram, or false otherwise.

1
2
3
4
def is_pangram(sentence):
    return len(set(sentence)) == 26
    # Time: O(n)
    # Space: O(1) - bound by 26 characters

268. Missing Number

Problem description - Easy

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

1
2
3
4
5
6
7
8
def missing_number(nums):
    num_set = set(nums)
    n = len(nums) + 1
    for number in range(n):
        if number not in num_set:
            return number
    # Time: O(n)
    # Space: O(n)

1426. Counting elements

Problem description - Easy

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately

1
2
3
4
5
6
7
def count_elements(arr):
    num_set = set(arr)
    count = 0
    for num in arr:
        if num + 1 in arr:
            count += 1
    return count

Counting

Using hash map to map keys to integers to track the frequency of things.

Example 1 - longest substring with at most k distinct characters

Problem description

You are given a string s and an integer k. Find the length of the longest substring that contains at most k distinct characters.

For example, given s = "eceba" and k = 2, return 3. The longest substring with at most 2 distinct characters is "ece"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import defaultdict
def longest_substring(s, k):
    # Condition: count(distinct c) <= k
    counts = defaultdict(int)
    left = ans = 0
    n = len(s)
    for right in range(n):
        counts[s[right]] += 1
        while len(counts) > k:
            counts[s[left]] -= 1
            if counts[s[left]] == 0:
                del counts[s[left]]
            left += 1
        ans = max(ans, right - left + 1)
    return ans
    # Time complexity of sliding window is `O(n)` if the work done in the for loop is amortized constant, which
    # is the case here, since hash map having `O(1)` operations
    # Space: The hash map will store at most k elements => O(k)

2248. Intersection of Multiple Arrays

Problem description - Easy

Given a 2D array nums that contains n arrays of distinct integers, return a sorted array containing all the numbers that appear in all n arrays.

For example, given nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]], return [3, 4]. 3 and 4 are the only numbers that are in all arrays.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import defaultdict
def find_arrays_intersect(nums):
    counts = defaultdict(int)
    for arr in nums:
        for num in arr:
            counts[num] += 1

    ans = [num for num in counts if counts[num] == len(nums)]
    return sorted(ans)
    # Time complexity: n lists, each list has m elements
    # Counting: O(n * m); ans can has max m elements => sorting 0(m * log m) => Total O(m(n+logm))
    # Space: If every element in the input is unique => hash map can have size of n*m => O(nm)

1941. Check if All Characters Have Equal Number of Occurrences

Problem description - Easy

Given a string s, determine if all characters have the same frequency.

For example, given s = "abacbc", return true. All characters appear twice. Given s = "aaabb", return false. "a" appears 3 times, "b" appears 2 times. 3 != 2

1
2
3
4
5
6
7
8
from collections import defaultdict
def check_character_same_freq(s):
    counts = defaultdict(int)
    for c in s:
        counts[c] += 1
    return len(set(counts.values())) == 1
    # Time: O(n) to populate hash map; O(n) to convert hash map to set => O(n)
    # Space: O(1) (bounded by 26 characters) or O(k) if k is the number of characters in the input (26)

Count the number of subarrays with an "exact" constraint

560. Subarray Sum Equals K

Problem description - Medium

Given an integer array nums and an integer k, find the number of subarrays whose sum is equal to k

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Constraint metric is sum => curr to track sum
# Using prefix sum and counts to map the prefix to frequency
# Go through counts if seeing curr - k; 
from collections import defaultdict
def subarray_exact_sum(nums, k):
    counts = defaultdict(int)
    counts[0] = 1 # since empty subarray has sum = 0
    curr = ans = 0
    for num in nums:
        curr += num
        # if we see curr - k in counts; and currently we are at curr prefix, meaning
        # the current subarray has sum = k => increase ans by 1
        if counts[curr - k]:
            ans += 1
        counts[curr] += 1
    return ans
    # Time: O(n)
    # Space: O(n)

1248. Count Number of Nice Subarrays

Problem description - Medium

Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# Constraint metric is odd number count => curr to track odd number count
# At each element, if curr - k exists; it means the current subsarray has k odd numbers => increase
# ans by 1
from collections import defaultdict
def subarray_exact_sum(nums, k):
    counts = defaultdict(int)
    counts[0] = 1 # since empty subarray has number of odd number = 0
    curr = ans = 0
    for num in nums:
        curr += num % 2
        # if we see curr - k in counts; and currently we are at curr prefix, meaning
        # the current subarray has sum = k => increase ans by 1
        ans += counts[curr - k]
        counts[curr] += 1
    return ans
    # Time: O(n)
    # Space: O(n)

2225. Find Players With Zero or One Losses

Problem description - Medium

You are given an integer array matches where \(matches[i] = [winner_i, loser_i]\) indicates that the player \(winner_i\) defeated player \(loser_i\) in a match.

Return a list answer of size 2 where:

  • answer[0] is a list of all players that have not lost any matches.
  • answer[1] is a list of all players that have lost exactly one match. The values in the two lists should be returned in increasing order.

Note:

  • You should only consider the players that have played at least one match.
  • The testcases will be generated such that no two matches will have the same outcome.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Constraint metric is odd number count => curr to track odd number count
# At each element, if curr - k exists; it means the current subsarray has k odd numbers => increase
# ans by 1
from collections import defaultdict
def list_players(matches):
    counts = {}
    for winner, loser in matches:
        counts[winner] = counts.get(winner, 0)
        counts[loser] = counts.get(loser, 0) + 1
    zero_loss = sorted([player for player in counts if counts.get(player) == 0])
    one_loss = sorted([player for player in counts if counts.get(player) == 1])
    return [zero_loss, one_loss]
    # Time: O(n*logn)
    # Space: O(n)

1133. Largest Unique Number

Problem description - Medium

Given an integer array nums, return the largest integer that only occurs once. If no integer occurs once, return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import defaultdict
def largest_unique_number(nums):
    counts = defaultdict(int)
    for num in nums:
        counts[num] += 1
    occur_once = [num for num in nums if counts[num] == 1]
    if len(occur_once):
        return max(occur_once)
    else:
        return -1
    # Time: O(n)
    # Space: O(n)

1189. Maximum Number of Balloons

Problem description - Easy

Given a string text, you want to use the characters of text to form as many instances of the word "balloon" as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from collections import defaultdict
def max_number_of_ballon(text):
    counts = defaultdict(int)
    for c in text:
        counts[c] += 1

    ans = min([2 * counts['a'], 2*counts['b'], 2*counts['n'], counts['l'], counts['o']])//2
    return ans
    # Time: O(n)
    # Space: O(1) - bounded by 26 that is constant

525. Contiguous Array

Problem description - Easy

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

A contiguous subarray is a subarray of an array with a condition that the elements of the subarray should be in exact sequence as the sequence of the elements in the array.

For example, array is [1,2,3,4,5] then [1,3,5] is a subarray of the array, but not a contiguous subarray since the sequence does not match as the elements 2 and 4 are skipped. [1,2,3] will be one of the contiguous subarrays.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def find_max_length(nums):
    # Use hash map to store the relative number of ones and zeros: curr when traverse the list with corresponding index
    # When see curr twice, meaning ones and zeros are equal between two indexes
    counts = {0: -1}
    ans = curr = 0
    for i, num in enumerate(nums):
        # Update curr (store relative number of ones and zeros): curr increase by 1 if see 1, else decrease by 1
        curr += 1 if num == 1 else -1
        # If we see curr twice, mean that number of ones and zeros are equal
        if curr in counts:
            # Update ans, max len will be the difference btw indexes
            ans = max(ans, i - counts[curr])
        else:
            counts[curr] = i
    return ans
    # Time: O(n)
    # Space: O(n)

Other hashing examples

49. Group Anagrams

Problem description - Medium

Given an array of strings strs, group the anagrams together.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once

For example, given strs = ["eat","tea","tan","ate","nat","bat"], return [["bat"],["nat","tan"],["ate","eat","tea"]].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
from collections import defaultdict
def group_anagrams(strs):
    # two strings are anagrams of each other is if they are equal after both being sorted.
    # Also, all strings in a group will be the same when sorted, so we can use the sorted version as a key.
    groups = defaultdict(list)
    for s in strs:
        sorted_str = "".join(sorted(s))
        groups[sorted_str].append(s)
    return list(groups.values())
    # Time: number of strings: n, average string length m
    # Sorted m log m; in loop of n iters => n m log m
    # Space: O(nm)

2260. Minimum Consecutive Cards to Pick Up

Problem description - Medium

You are given an integer array cards where cards[i] represents the value of the ith card. A pair of cards are matching if the cards have the same value.

Return the minimum number of consecutive cards you have to pick up to have a pair of matching cards among the picked cards. If it is impossible to have matching cards, return -1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def minimum_card_pickup(cards):
    ans = float('inf')
    seen = dict()
    for right, card in enumerate(cards):     
        if card in seen:
            ans = min(ans, right - seen[card] + 1)
        seen[card] = right
    return ans if ans != float('inf') else -1
    # Time: O[n]
    # Space: O[n]

2342. Max Sum of a Pair With Equal Sum of Digits

Problem description - Medium

Given an array of integers nums, find the maximum value of nums[i] + nums[j], where nums[i] and nums[j] have the same digit sum (the sum of their individual digits). Return -1 if there is no pair of numbers with the same digit sum.

Solution 1 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import defaultdict
def max_same_digit_sum(nums):
    def get_digit_sum(num):
        digit_sum = 0
        while num:
            digit_sum += num % 10
            num //= 10

        return digit_sum

    hash_map = defaultdict(list)
    for num in nums:     
        digit_sum = get_digit_sum(num)
        hash_map[digit_sum].append(num)

    ans = -1
    for curr in hash_map.values():
        if len(curr) > 1:
            curr.sort(reverse=True)
            ans = max(ans, curr[0] + curr[1])

    return ans
# This is not efficient due to the sorting, could be potentially cost O(n*log(n)) if all number has same digit sum.
Solution 2: not store the whole list, only the max number for each digit sum 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from collections import defaultdict
def max_same_digit_sum(nums):
    def get_digit_sum(num):
        digit_sum = 0
        while num:
            digit_sum += num % 10
            num //= 10

        return digit_sum

    hash_map = defaultdict(int)
    ans = -1
    for num in nums:     
        digit_sum = get_digit_sum(num)
        if digit_sum in hash_map:
            ans = max(ans, num + hash_map[digit_sum])
        hash_map[digit_sum] = max(hash_map[digit_sum], num)

    return ans
# Time O(n), space O(n)

2352. Equal Row and Column Pairs

Problem description - Medium

Given an n x n matrix grid, return the number of pairs (R, C) where R is a row and C is a column, and R and C are equal if we consider them as 1D arrays.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import defaultdict
def number_of_pairs(grid):
    # Use a hash map to count how many times each row occurs; another hash map to count columns
    # Iterate over row hash map, check if the array appears as a column, if yes, add the product of appearances to ans
    ans = 0
    n = len(grid)
    m = len(grid[0])
    # Count row appearances
    row_count = defaultdict(int)
    for row in grid:
        row_count[tuple(row)] += 1
    # Count column appearances
    column_count = defaultdict(int)
    for j in range(m):
        column = []
        for i in range(n):
            column.append(grid[i][j])
        column_count[tuple(column)] += 1
    # Iterate over row_count and calculate sum
    for key in row_count:
        ans += row_count[key] * column_count[key]

    return ans
    # Time: O[n^2]
    # Space: O[n^2]