Basics
This chapter covers fundamental data structures that enable O(1) operations - the building blocks for efficient algorithm design.
Set
set(): enables `O(1)` add, remove, and lookup. Stores unique keys.
my_set = set()
my_set.add(1) # Add element
my_set.remove(1) # Remove element
1 in my_set # O(1) lookupMap / Dict
{} or dict(): enables `O(1)` add, remove, lookup. The difference with a set is that it not only stores unique keys, but also a corresponding value associated with each unique key.
my_map = {}
my_map[key] = value # Add/update
del my_map[key] # Remove
key in my_map # O(1) lookupDefaultdict
defaultdict is oftentimes a better version of map. The difference is that Map will throw a KeyError if you try to access a key that is not present in the map, while a defaultdict initializes a default value so it will never throw a key error. If you try to access a non-initialized value, it will simply return the default, which you can define.
from collections import defaultdict
defaultdict(int) # Default value: 0
defaultdict(list) # Default value: []
defaultdict(lambda: inf) # Default value: inf
defaultdict(lambda: [0]) # Default value: [0]
defaultdict(lambda: defaultdict(int)) # 2D default dictCounter
Counter is just a simple version of a dict that easily gets the frequency count in one call. Note that counters act as defaultdicts, in that they don't throw key errors, and will default to a frequency of 0.
Ie. Counter([1,2,3,1]) returns a map: {1:2, 2:1, 3:1}, which is a list of pairs (key, frequency of that key in the array).
from collections import Counter
# Without Counter:
freq = {}
for a in A:
if a in freq:
freq[a] += 1
else:
freq[a] = 1
# With defaultdict:
freq = defaultdict(int)
for a in A:
freq[a] += 1
# With Counter (simplest):
freq = Counter(A)Two Sum Pattern
The Two Sum pattern is a classic technique that uses a hash map to find pairs with a target relationship. Instead of O(n²) brute force, we achieve O(n) by storing previously seen values.
The clever insight is: if we consider the second element j in a pair (i,j), and we've stored all values nums[i] for i < j in a map, we can simply search in `O(1)` for target - nums[j] = nums[i] as this is deterministic.
01Two SumEasy
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.
def twoSum(self, nums: List[int], target: int) -> List[int]:
index = {}
for i in range(len(nums)):
if target - nums[i] in index:
return [index[target-nums[i]], i]
index[nums[i]] = i
return -1O(n)O(n)We can brute force this in `O(n²)` time and `O(1)` space, checking the formula: nums[i] + nums[j] == target. However with the hash map approach, we store the index mapping which gives us the original index i.
Subarray Sum Problems
These problems extend the Two Sum idea to subarrays using prefix sums. The key insight is that a subarray sum can be computed as the difference of two prefix sums.
We maintain a frequency counter mapping prefix_sums -> frequency count. Initialize the empty prefix with sum 0 with frequency 1 (important: what if the target subarray is a prefix itself?). On every iteration, search for prefix_sum - k in the map.
Subarray Sum Visualization
Looking for subarrays with sum k = 4, current prefix sum = 7
- Imagine we are at index i with prefix sum = 7
- If we search for prefix sums equal to 7-4 = 3...
- These prefix sums with value 3 will carve out a subarray ending at index i with sum equal to 4!
- This is the same as Two Sum, just spread over an array rather than a single value.
01Subarray Sum Equals KMedium
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
def subarraySum(self, nums: List[int], k: int) -> int:
prev_sum = Counter({0:1}) # sum -> frequency
n, prefix_sum, res = len(nums), 0, 0
for i in range(n):
prefix_sum += nums[i]
res += prev_sum[prefix_sum - k]
prev_sum[prefix_sum] += 1
return resO(n)O(n)Brute force is O(n³) time O(1) space. You can get O(n²) using prefix sums. But this O(n) solution uses the Two Sum insight!
Why can we have multiple prefix sums with the same value? Because we allow 0's and negatives. Example: [3, 0, -1, 1] forms 3 prefix sums with value 3: ([3], [3,0], [3,0,-1,1])
Note: If the problem only allowed non-negative numbers, we could use a sliding window as an O(n) time and O(1) space solution.
02Binary Subarrays With SumMedium
Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal.
A subarray is a contiguous part of the array.
# This is just an easier case of Q560 - exact same code works!
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
return self.subarraySum(nums, goal)O(n)O(n)Notice that this is actually just an easier case of Q560 Subarray Sum Equals K. The exact same code works here.
03Subarray Sums Divisible by KMedium
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
def subarraysDivByK(self, nums: List[int], k: int) -> int:
# [ pref ][ 0 ]
# [ pref ][ 0 ]
# [ pref ]
# For all indices j < i where pref[j] == pref[i]:
# the subarray [j+1,i] is divisible by k.
pref_mods = Counter({0:1}) # pref_mod -> freq
pref, res = 0, 0
for i in range(len(nums)):
pref = (pref + nums[i]) % k
res += pref_mods[pref]
pref_mods[pref] += 1
return resO(n)O(k)This is the exact same idea - we track prefix sums modulo k. If two prefix sums have the same remainder, their difference is divisible by k.
04Number of Sub-arrays With Odd SumMedium
Given an array of integers arr, return the number of subarrays with an odd sum.
Since the answer can be very large, return it modulo 10⁹ + 7.
def numOfSubarrays(self, arr: List[int]) -> int:
even_odd_prefix_sum, prefix_sum, res = [1, 0], 0, 0
for a in arr:
prefix_sum += a
even_odd_prefix_sum[prefix_sum % 2] += 1
res = (res + even_odd_prefix_sum[not (prefix_sum % 2)]) % (10**9+7)
return resO(n)O(1)This is the exact same idea as before. If the current prefix sum is odd, a previous even prefix sum carves out an odd subarray sum. If the current prefix sum is even, a previous odd prefix sum carves out an odd subarray sum.
05Continuous Subarray SumMedium
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
• its length is at least two, and
• the sum of the elements of the subarray is a multiple of k.
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
prefix_index = {0: -1}
pref = 0
for i in range(len(nums)):
pref = (pref + nums[i]) % k
if pref in prefix_index:
if i - prefix_index[pref] >= 2:
return True
else:
prefix_index[pref] = i # store EARLIEST index
return FalseO(n)O(min(n,k))Instead of a frequency count, we want an existence check. So our map values are the indices rather than frequency counts.
Key: Only update the prefix index map with the earliest index with that prefix sum. We want to greedily check for the largest possible subarray.
06Make Sum Divisible by PMedium
Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.
Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.
def minSubarray(self, nums: List[int], p: int) -> int:
k = sum(nums) % p
if k == 0:
return 0 # edge case
n = len(nums)
prefsum_to_index = {0: -1}
pref_sum = 0
res = inf
for i in range(n):
pref_sum = (pref_sum + nums[i]) % p
if (pref_sum - k) % p in prefsum_to_index:
res = min(res, i - prefsum_to_index[(pref_sum - k) % p])
prefsum_to_index[pref_sum] = i
return res if res != n else -1O(n)O(n)The diagram:
# [ pref_sum % p ]
# [ (pref_sum-k)%p ][k%p]
# [ k % p ]
We want the LATEST INDEX of prefix subarray that has mod (a-k)%p, since this will minimize the length of the (k%p) subarray.
Searching for (pref_sum - k) % p will carve out a subarray of sum k % p, which when removed leaves sum 0 % p.
07Count Number of Nice SubarraysMedium
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.
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
# Transform: each number = 0 if even, 1 if odd
nums = [num % 2 for num in nums]
return self.subarraySum(nums, k)
def subarraySum(self, nums: List[int], k: int) -> int:
prev_sum = Counter({0:1})
n, prefix_sum, res = len(nums), 0, 0
for i in range(n):
prefix_sum += nums[i]
if prefix_sum - k in prev_sum:
res += prev_sum[prefix_sum - k]
prev_sum[prefix_sum] += 1
return resO(n)O(n)The interesting point here is that we can make a simple transformation of nums to a boolean array indicating the parity of each element. Then a sum equal to k means a subarray with k odd elements.
08Count of Interesting SubarraysMedium
You are given a 0-indexed integer array nums, an integer modulo, and an integer k.
A subarray nums[l..r] is interesting if:
• Let cnt be the number of indices i in the range [l, r] such that nums[i] % modulo == k
• Then, cnt % modulo == k
Return an integer denoting the count of interesting subarrays.
def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
nums = [num % modulo == k for num in nums]
return self.subarraySum(nums, modulo, k)
def subarraySum(self, nums: List[int], mod: int, k: int) -> int:
prev_sum = Counter({0:1}) # size mod
n, prefix_sum, res = len(nums), 0, 0
for i in range(n):
prefix_sum += nums[i]
if (prefix_sum - k) % mod in prev_sum:
res += prev_sum[(prefix_sum - k) % mod]
prev_sum[prefix_sum % mod] += 1 # mod here!
return resO(n)O(min(n, mod))This is exactly the same question as before, the wording is just confusing. Transform each element to a boolean value if it is congruent to k % mod. Now a subarray sum of k % mod means that subarray is 'interesting'.
Anagrams
Anagrams are defined as two strings who have the same letters but are in a different order - ie. permutations of each other.
Example: eat, tea, ate are all anagrams of each other.
Key Property: Anagrams in sorted order are the same string. Sorting each of {eat, tea, ate} = {aet, aet, aet}.
01Valid AnagramEasy
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
# Method 1: Compare sorted counters
def isAnagram(self, s: str, t: str) -> bool:
return sorted(Counter(s).items()) == sorted(Counter(t).items())
# Method 2: Compare sorted strings
def isAnagram(self, s: str, t: str) -> bool:
return sorted(s) == sorted(t)
# Method 3: Compare counters directly
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# Method 4: Decrement counter
def isAnagram(self, s: str, t: str) -> bool:
freq = Counter(s)
for c in t:
freq[c] -= 1
if freq[c] == 0:
del freq[c]
return not freqO(n+m)O(n+m)There are a few ways to do this using sorting and counters. The O(n log n) sorting approach is also valid.
02Group AnagramsMedium
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
# Method 1: Use sorted word as key
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_to_words = defaultdict(list)
for word in strs:
anagram_to_words[tuple(sorted(word))].append(word)
return list(anagram_to_words.values())
# Method 2: Use sorted counter as key
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
anagram_to_words = defaultdict(list)
for word in strs:
anagram_to_words[tuple(sorted(Counter(word).items()))].append(word)
return list(anagram_to_words.values())O(n * m log m)O(n * m)We can group anagrams using their sorted word as key, and append the original word as part of the value list. Here n = len(strs), m = average string length.
Sets / Contains Duplicate
We can use sets for many purposes. One useful one is to check for duplicates. This applies in many contexts such as visited sets in graph traversals.
01Contains DuplicateEasy
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
def containsDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)O(n)O(n)Very simple - if there is any duplicate, the set will combine those duplicates into a single element so the length will be less than the original.
02Contains Duplicate IIEasy
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
# Method 1: With explicit check
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
last = {}
for i in range(len(nums)):
if nums[i] in last and i - last[nums[i]] <= k:
return True
last[nums[i]] = i
return False
# Method 2: With defaultdict
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
last = defaultdict(lambda: -inf)
for i in range(len(nums)):
if i - last[nums[i]] <= k:
return True
last[nums[i]] = i
return FalseO(n)O(n)This problem is actually very similar to Two Sum - we track the last index we saw each value and check if the distance constraint is satisfied.
Cycle Permutations
A famous problem is determining the minimum number of swaps to sort an array. We can solve this by:
1. Sorting the array
2. Constructing a graph representing the movements required to get sorted order (ie. move index 0 to index 3)
3. This decomposes the graph into a list of cycles
4. The min number of swaps is simply sum_{cycle c}(length(c) - 1)
Example: We want to move 0 → 1 and 1 → 0. This cycle is length 2, so we just need a single swap to fix this.
01Minimum Swaps to Sort by Digit SumMedium
You are given an array nums of distinct positive integers. You need to sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order.
Return the minimum number of swaps required to rearrange nums into this sorted order.
A swap is defined as exchanging the values at two distinct positions in the array.
def digitSum(self, num):
return sum(int(d) for d in str(num))
def minSwaps(self, nums):
n = len(nums)
# Sort based on (digit sum, value)
sorted_nums = sorted(nums, key=lambda x: (self.digitSum(x), x))
# Map original indices to sorted positions
index_map = {val: i for i, val in enumerate(sorted_nums)}
visited = [False] * n
swaps = 0
for i in range(n):
if visited[i] or index_map[nums[i]] == i:
continue
cycle_size = 0
j = i
while not visited[j]:
visited[j] = True
j = index_map[nums[j]]
cycle_size += 1
if cycle_size > 0:
swaps += cycle_size - 1
return swapsO(n log n)O(n)Note in this example we don't just want regular sorted order, but sorted order depending on the digit sum. The cycle decomposition technique works regardless of the sorting criteria.