Arrays & Hash Maps
The two data structures behind most interview problems — and when to use each
Knowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
Two data structures solve the majority of algorithmic problems. Knowing their tradeoffs is fundamental.
Arrays (Python lists):
Access by index: O(1) lst[i] Append: O(1)* lst.append(x) *amortized Insert at index: O(n) lst.insert(0, x) — shifts everything Delete at index: O(n) del lst[0] — shifts everything Search: O(n) x in lst
Hash Maps (Python dicts/sets):
Insert: O(1) average d[key] = val Lookup: O(1) average d[key] Delete: O(1) average del d[key] Search: O(1) average key in d
The swap: trade space for time
```python # Problem: find if any two numbers in a list sum to target
# O(n²) — check all pairs def two_sum_slow(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)
# O(n) — use a hash map to remember what we've seen def two_sum_fast(nums, target): seen = {} # value → index for i, n in enumerate(nums): complement = target - n if complement in seen: # O(1) lookup return (seen[complement], i) seen[n] = i ```
Two-pointer technique — works on sorted arrays, O(n): ``python def two_sum_sorted(nums, target): left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return (left, right) elif s < target: left += 1 else: right -= 1 return None
Sliding window — find a subarray satisfying a condition: ``python def max_sum_subarray(nums, k): window = sum(nums[:k]) best = window for i in range(k, len(nums)): window += nums[i] - nums[i - k] # slide: add right, remove left best = max(best, window) return best
Examples
Frequency counting with dict
Counter is a dict subclass that makes frequency problems trivial
from collections import Counter
def most_common_words(text: str, n: int) -> list[tuple[str, int]]:
words = text.lower().split()
counts = Counter(words) # O(n) to build
return counts.most_common(n) # O(k log k) to sort
text = "the quick brown fox jumps over the lazy dog the fox"
print(most_common_words(text, 3))
# [('the', 3), ('fox', 2), ('quick', 1)]Group anagrams — hash map key design
Key insight: anagrams have the same characters — use sorted tuple as hash key
from collections import defaultdict
def group_anagrams(words: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for word in words:
key = tuple(sorted(word)) # anagrams have same sorted letters
groups[key].append(word)
return list(groups.values())
words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(words))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]Next in Algorithms & Data Structures
Sorting Algorithms