The two most-used structures: the array, contiguous memory with O(1) indexing, and the hash table, O(1) average lookup. Learn their costs and the single most powerful trick in DSA — trading space for time with a hash map.
An array stores elements in contiguous memory, so accessing any index is O(1) — the address is computed directly. The cost shows up on structural change: inserting or deleting in the middle must shift everything after it, which is O(n). Python’s list is a dynamic array; appending is amortized O(1) because it occasionally resizes, but inserting at the front is O(n).
a = [10, 20, 30, 40]
a[2] # O(1) — direct index, address computed from position
a.append(50) # amortized O(1) — occasionally resizes + copies
a.pop() # O(1) — remove from the end
a.insert(0, 5) # O(n) — must SHIFT every element right
a.pop(0) # O(n) — must shift every element left
30 in a # O(n) — no shortcut; scans until found
# takeaway: arrays are great for index access + end operations,
# poor for inserts/deletes in the middle or front.A hash table (Python’s dict and set) stores keys by running them through a hash function to compute where to put them, giving average O(1) insert, lookup, and delete. This near-constant-time membership test is the workhorse of efficient algorithms. The trade-off is memory and unordered storage, and worst-case O(n) if many keys collide (rare in practice).
d = {} # dict = hash table (key -> value)
d["ann"] = 42 # O(1) average insert
d["ann"] # O(1) average lookup
"ann" in d # O(1) average membership <- the superpower
del d["ann"] # O(1) average delete
s = set() # set = hash table of keys only
s.add(7); 7 in s # O(1) average
# vs a list: "x in list" is O(n). "x in set/dict" is O(1) average.
# That single difference turns many O(n^2) solutions into O(n).The most common optimization in all of DSA is replacing a repeated linear search with a hash-map lookup. The classic example is Two Sum: the brute force checks every pair in O(n²), but storing each number you have seen in a hash map lets you find the complement in O(1), solving it in a single O(n) pass. Recognizing when a hash map collapses a nested loop is a defining skill.
# Two Sum: find indices of two numbers that add to target.
# brute force — check every pair: O(n^2)
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]
# hash map — remember what you've seen; look up the complement: O(n)
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen: # O(1) — is the complement here?
return [seen[target - x], i]
seen[x] = i
return None
# O(n) time, O(n) space. The nested loop is gone.Hash maps also make counting and grouping trivial and fast. Tallying frequencies, finding the most common element, or grouping items by a key are all single O(n) passes. Python’s collections module (Counter, defaultdict) provides these directly — knowing them turns many problems into a few lines.
from collections import Counter, defaultdict
# frequency count in one pass — O(n)
counts = Counter("mississippi") # {'i':4,'s':4,'p':2,'m':1}
counts.most_common(1) # [('i', 4)]
# group words by a key (e.g. anagrams share a sorted-letter key) — O(n * klogk)
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
key = "".join(sorted(w)) # anagrams -> same key
groups[key].append(w)
return list(groups.values())
group_anagrams(["eat","tea","tan","ate","nat"])
# [['eat','tea','ate'], ['tan','nat']]A prefix-sum array is a small precomputation that answers "sum of any range" in O(1) instead of O(n) per query. You spend O(n) once to build cumulative totals, then every range sum is one subtraction. It is a representative array technique: do work up front so repeated questions become cheap — the same idea behind database indexes and caching.
# answer many "sum of nums[i..j]" queries fast.
def build_prefix(nums):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x) # cumulative totals, O(n) once
return prefix
def range_sum(prefix, i, j): # inclusive i..j
return prefix[j+1] - prefix[i] # O(1) per query!
nums = [3, 1, 4, 1, 5, 9]
p = build_prefix(nums) # [0,3,4,8,9,14,23]
range_sum(p, 1, 3) # 1+4+1 = 6, in O(1)
# without prefix sums, each query re-scans the range = O(n) each.