Day 1 · Topic 1
Arrays & Hashing
The most fundamental pattern. Use a HashMap or
HashSet to trade O(n) space for O(1) lookup time.
This converts O(n²) brute-force solutions into O(n).
// Core Pattern
Before any nested loop, ask: "Can I store previously seen values in a hash map/set and look them up in O(1)?" This single question eliminates O(n²) solutions for 80% of array problems.
9
Problems
1.5h
Est. Time
Day 1
Schedule
KEY INSIGHT: Store seen values in a set. Set lookup is O(1). If a value is already in the set → duplicate.
Pattern: HashSet Optimal: O(n) Space: O(n)
BRUTE FORCE
def containsDuplicate(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] == nums[j]:
return True
return False
# Time: O(n²) | Space: O(1)
OPTIMAL SOLUTION
def containsDuplicate(nums):
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
# One-liner: return len(nums) != len(set(nums))
# Time: O(n) | Space: O(n) KEY INSIGHT: Count frequency of each char in s, decrement for t. Any negative → mismatch.
Pattern: HashMap / Counter Optimal: O(n) Space: O(1) — only 26 chars
BRUTE FORCE
def isAnagram(s, t):
return sorted(s) == sorted(t)
# Time: O(n log n) | Space: O(n)
OPTIMAL SOLUTION
def isAnagram(s, t):
if len(s) != len(t): return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
return all(c == 0 for c in count)
# Time: O(n) | Space: O(1) KEY INSIGHT: For each number, check if target - num was already seen. Store value→index in a HashMap.
Pattern: HashMap (value → index) Optimal: O(n) Space: O(n)
BRUTE FORCE
def twoSum(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# Time: O(n²) | Space: O(1)
OPTIMAL SOLUTION
def twoSum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
# Time: O(n) | Space: O(n) KEY INSIGHT: Sort each string → its canonical anagram key. Group by key.
Pattern: HashMap with sorted key Optimal: O(n·k·log k) Space: O(n·k)
BRUTE FORCE
# O(n² · k) — compare every pair
def groupAnagrams(strs):
groups = []
used = [False] * len(strs)
for i in range(len(strs)):
if used[i]: continue
group = [strs[i]]
for j in range(i+1, len(strs)):
if sorted(strs[i]) == sorted(strs[j]):
group.append(strs[j])
used[j] = True
groups.append(group)
return groups
OPTIMAL SOLUTION
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # or: tuple(char_count)
groups[key].append(s)
return list(groups.values())
# Even faster O(n·k) key using char counts:
def groupAnagrams_v2(strs):
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values()) KEY INSIGHT: Max frequency = n (all same). Use index as frequency bucket. Iterate from high freq down.
Pattern: Bucket Sort Optimal: O(n) Space: O(n)
BRUTE FORCE
from collections import Counter
def topKFrequent(nums, k):
return [x for x, _ in Counter(nums).most_common(k)]
# Time: O(n log n) | Space: O(n)
OPTIMAL SOLUTION
def topKFrequent(nums, k):
count = {}
freq = [[] for _ in range(len(nums) + 1)] # bucket[i] = nums with freq i
for n in nums:
count[n] = count.get(n, 0) + 1
for n, c in count.items():
freq[c].append(n)
result = []
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
result.append(n)
if len(result) == k:
return result
# Time: O(n) | Space: O(n) KEY INSIGHT: output[i] = (product of all left of i) × (product of all right of i). Two passes, no division.
Pattern: Prefix × Suffix product Optimal: O(n) Space: O(1) (output array doesn't count)
BRUTE FORCE
def productExceptSelf(nums):
result = []
for i in range(len(nums)):
prod = 1
for j in range(len(nums)):
if j != i: prod *= nums[j]
result.append(prod)
return result
# Time: O(n²) | Space: O(n)
OPTIMAL SOLUTION
def productExceptSelf(nums):
n = len(nums)
output = [1] * n
# Forward pass: output[i] = product of nums[0..i-1]
prefix = 1
for i in range(n):
output[i] = prefix
prefix *= nums[i]
# Backward pass: multiply by product of nums[i+1..n-1]
suffix = 1
for i in range(n - 1, -1, -1):
output[i] *= suffix
suffix *= nums[i]
return output
# Example: [1,2,3,4] → after prefix: [1,1,2,6], after suffix: [24,12,4,1]
# Time: O(n) | Space: O(1) KEY INSIGHT: Box index = (row//3)*3 + (col//3). Check each cell against its row, column, and box set.
Pattern: HashSet for rows/cols/boxes Optimal: O(81) = O(1) Space: O(81) = O(1)
BRUTE FORCE
# Same approach — board is fixed 9×9 so no real brute force difference
OPTIMAL SOLUTION
def isValidSudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
val = board[r][c]
if val == '.': continue
box = (r // 3) * 3 + (c // 3)
if val in rows[r] or val in cols[c] or val in boxes[box]:
return False
rows[r].add(val)
cols[c].add(val)
boxes[box].add(val)
return True
# Time: O(1) | Space: O(1) — board is always 9×9 KEY INSIGHT: Prefix each string with its length + a delimiter (e.g. '4#word'). On decode, read length, skip delimiter, extract.
Pattern: Length-prefix encoding Optimal: O(n) Space: O(n)
BRUTE FORCE
# Using a special delimiter (breaks if strings contain the delimiter)
def encode(strs): return "|||".join(strs)
def decode(s): return s.split("|||")
OPTIMAL SOLUTION
def encode(strs):
# Format: "<length>#<string>" for each string
return "".join(f"{len(s)}#{s}" for s in strs)
def decode(s):
result = []
i = 0
while i < len(s):
j = s.index('#', i) # find the '#' delimiter
length = int(s[i:j]) # read the length
result.append(s[j+1:j+1+length]) # extract the string
i = j + 1 + length
return result
# Time: O(n) | Space: O(n) KEY INSIGHT: Only count a sequence starting from a number with no predecessor (n-1 not in set). Amortised O(n).
Pattern: HashSet — start of sequence only Optimal: O(n) Space: O(n)
BRUTE FORCE
def longestConsecutive(nums):
nums.sort()
longest, curr = 0, 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1] + 1: curr += 1
elif nums[i] != nums[i-1]: curr = 1
longest = max(longest, curr)
return longest
# Time: O(n log n) | Space: O(1)
OPTIMAL SOLUTION
def longestConsecutive(nums):
num_set = set(nums)
longest = 0
for n in num_set:
if (n - 1) not in num_set: # n is a sequence START
length = 1
while (n + length) in num_set:
length += 1
longest = max(longest, length)
return longest
# Time: O(n) amortized | Space: O(n)
# Why O(n)? Each number is visited at most twice (once as start check, once in while loop).