Python Essentials for DSA
The exact slice of Python you need for interviews, including the built-in costs that quietly turn an O(n) solution into O(n²).
12 min readUpdated 2026-09-01pythonfundamentals
Why this lesson exists
Every solution in this course is written in Python. You do not need to be a Python expert — but you do need to know which operations are cheap and which are secretly expensive.
The most common interview failure is not a wrong algorithm. It is a correct algorithm made quadratic by one innocent-looking line.
Lists
A Python list is a dynamic array — contiguous memory that grows as needed.
python
nums = [3, 1, 4, 1, 5]
nums[0] # 3 O(1)
nums[-1] # 5 O(1) — negative indexes count from the end
len(nums) # 5 O(1)
nums.append(9) # O(1) amortised
nums.pop() # 9 O(1) — from the END
The costs that matter
| Operation | Cost | Note |
|---|---|---|
lst[i] | ||
lst.append(x) | amortised | |
lst.pop() | from the end | |
lst.pop(0) | shifts everything left | |
lst.insert(0, x) | shifts everything right | |
x in lst | scans the whole list | |
lst[a:b] | slicing copies | |
sorted(lst) |
The three bolded rows cause most accidental solutions.
python
# ❌ O(n²) — pop(0) shifts every remaining element each time
while queue:
item = queue.pop(0)
# ✅ O(n) — deque pops from the left in O(1)
from collections import deque
queue = deque(items)
while queue:
item = queue.popleft()
Slicing copies
python
def bad_sum(nums):
if not nums:
return 0
return nums[0] + bad_sum(nums[1:]) # ❌ copies the rest EVERY call
nums[1:] builds a new list each time — total. Pass an index instead:
python
def good_sum(nums, i=0):
if i == len(nums):
return 0
return nums[i] + good_sum(nums, i + 1) # ✅ no copying
List comprehensions
python
squares = [x * x for x in range(5)] # [0, 1, 4, 9, 16]
evens = [x for x in nums if x % 2 == 0] # with a filter
grid = [[0] * 3 for _ in range(4)] # 4×3 of zeros
⚠️ The 2D list trap. This is a genuine interview-killer:
python
grid = [[0] * 3] * 4 # ❌ four references to the SAME row
grid[0][0] = 9
print(grid) # [[9,0,0], [9,0,0], [9,0,0], [9,0,0]]
* 4 copies the reference, not the list. Always use a comprehension:
python
grid = [[0] * 3 for _ in range(4)] # ✅ four independent rows
Dictionaries and sets
Both are hash tables: average lookup, insert and delete.
python
counts = {}
counts['a'] = 1
counts['a'] += 1
'a' in counts # O(1) — vs O(n) for a list
counts.get('z', 0) # 0 instead of KeyError
defaultdict and Counter
python
from collections import defaultdict, Counter
# Grouping without checking whether the key exists
groups = defaultdict(list)
for word in words:
groups[''.join(sorted(word))].append(word)
# Counting in one line
freq = Counter("hello") # {'l': 2, 'h': 1, 'e': 1, 'o': 1}
freq.most_common(2) # [('l', 2), ('h', 1)]
Counter is a genuine shortcut in interviews — anagram and frequency problems become two lines.
Sets
python
seen = set()
seen.add(3)
3 in seen # O(1)
a, b = {1,2,3}, {2,3,4}
a & b # {2, 3} intersection
a | b # {1,2,3,4} union
a - b # {1} difference
{} creates an empty dict, not a set. Use set().
Strings are immutable
Every "modification" builds a whole new string.
python
# ❌ O(n²) — a new string on every iteration
result = ""
for word in words:
result += word
# ✅ O(n) — collect, then join once
result = "".join(words)
pop(0), and just as common.
Useful methods:
python
s.split() # split on whitespace
s.strip() # trim both ends
s.lower()
s.replace('a', 'b')
s.isalnum() # useful for palindrome filtering
"".join(reversed(s)) # or simply s[::-1]
Tuples
Immutable, and therefore hashable — so they can be dictionary keys and set members.
python
point = (3, 4)
x, y = point # unpacking
seen = {(0, 0), (1, 2)} # a set of coordinates
memo[(row, col)] = value # a tuple as a dict key
(r, c) tuples for visited sets.
The tools that save time
enumerate — index and value together
python
for i, value in enumerate(nums):
print(i, value)
for i, value in enumerate(nums, start=1): # 1-based
print(i, value)
zip — walk several sequences at once
python
for name, score in zip(names, scores):
print(name, score)
zip stops at the shortest sequence.
sorted with a key
python
sorted(words, key=len) # by length
sorted(people, key=lambda p: p['age']) # by a field
sorted(nums, reverse=True) # descending
# Sort by one key ascending, another descending
sorted(items, key=lambda x: (x[0], -x[1]))
That last pattern — a tuple key with a negation — comes up constantly.
heapq — the priority queue
python
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappop(heap) # smallest
# Python has NO max-heap: negate the values
heapq.heappush(heap, -value)
largest = -heapq.heappop(heap)
deque — a real queue
python
from collections import deque
q = deque([1, 2, 3])
q.append(4) # right, O(1)
q.appendleft(0) # left, O(1)
q.popleft() # left, O(1) ← this is what lists cannot do
Gotchas that bite
Mutable default arguments
python
def add(item, target=[]): # ❌ the SAME list across all calls
target.append(item)
return target
add(1) # [1]
add(2) # [1, 2] ← surprise!
None:
python
def add(item, target=None): # ✅
if target is None:
target = []
target.append(item)
return target
memo={} default.
Integer division
python
7 / 2 # 3.5 float division
7 // 2 # 3 floor division
-7 // 2 # -4 floors DOWN, not toward zero
-3); Python floors (-4). This causes subtle bugs when porting binary search or midpoint code.
is vs ==
python
a == b # same value
a is b # same object in memory
== for values, is only for None, True, False.
Copying
python
a = [1, 2, 3]
b = a # ❌ same list, both names point at it
b = a[:] # ✅ shallow copy
b = a.copy() # ✅ same thing
import copy
b = copy.deepcopy(nested) # for nested structures
Recursion depth
python
import sys
sys.setrecursionlimit(10000) # default is ~1000
Deep recursion on a large tree will hit this. Mention it if your solution recurses deeply.
Try it
Spot the O(n²)python
Loading editor…
word not in seen is on a list — use a set.
Bug 2: result += word rebuilds the string each time — collect into a list and join.
Both fixed, the function is instead of .
Quick reference
| Need | Use |
|---|---|
| Fast membership test | set |
| Count things | Counter |
| Group things | defaultdict(list) |
| Queue (FIFO) | deque |
| Stack (LIFO) | plain list |
| Priority queue | heapq |
| Build a string | "".join(parts) |
| Dict/set key | tuple, never a list |
Common mistakes
pop(0)orinsert(0, x)on a list — usedeque.x in listinside a loop — use a set.+=on strings in a loop — usejoin.[[0]*n]*mfor a 2D grid — every row is the same object.- Mutable default arguments.
- Slicing in recursion, which copies each call.
{}for an empty set — that is a dict.- Assuming
-7 // 2 == -3— Python floors to-4.
Summary
Know the cost of every built-in you reach for. Lists are fast at the end and slow at the front; usedeque for queues, set for membership, Counter for frequencies, and join for strings. Avoid mutable defaults and the [[0]*n]*m trap, and remember that slicing copies.