Python Data Structures & Time Complexity Reference Guide

This guide serves as a quick reference for Python data structures, their operations, and time complexities. Essential for coding interviews, LeetCode problems, and writing efficient algorithms.

Best Practices & Tips

Before Updating Data Types

Always check if a data structure is empty before updating:

# Good practice
if nums:
    nums[0] = value

# Or
if len(nums) > 0:
    nums[0] = value

Reverse Iteration

Don’t use -i or minus indexing for reverse iteration. Instead, use range():

# Avoid
for i in range(len(nums) - 1, -1, -1):
    # This is less clear

# Better
for i in range(len(nums) - 1, -1, -1):
    # Explicit and clear
    print(nums[i])

The ord() Function

The ord() function in Python converts a single Unicode character into its corresponding integer Unicode code point value.

ord('A')  # Returns 65
ord('a')  # Returns 97
ord('0')  # Returns 48

Nested Loops

You can nest loops only when you will iterate through all items once. If both loops iterate through all items once, the solution is still O(n) where n is the total number of elements.

# O(n) - both loops iterate through all items once
for item in list1:
    for nested_item in list2:
        # process

Matrix Operations

When working with matrices, remember:

• Linear index of last element: ROWS * COLUMNS - 1
• For any given linear index:
  • row = linear_index // COLUMNS
  • col = linear_index % COLUMNS

# Example: 3x4 matrix
ROWS, COLS = 3, 4
linear_index = 11  # Last element
row = 11 // 4  # 2
col = 11 % 4   # 3

Array (List) - Mutable

Arrays in Python are implemented as dynamic arrays (lists).

Common Operations

1. Access: array[index] - O(1)
2. Update: array[index] = value - O(1)
3. Append: array.append(item) - O(1) amortized
4. Insert: array.insert(index, item) - O(n)
5. Remove by index: array.pop(index) - O(n)
6. Remove first occurrence: array.remove(item) - O(n)
7. Find item: value in array - O(n)
8. Find first occurrence: array.index(value, start, end) - O(n)
9. Slicing: array[start:end:steps] - O(k) where k is slice size
10. Copy: array.copy() or list(array) or array[:] - O(n)
11. Sort: array.sort() - O(n log n)
12. Reverse: array.reverse() - O(n)
13. Concatenation: array1 + array2 or array1.extend(array2) - O(n+m)
14. Filter: [x for x in array if condition] - O(n)

Examples

nums = [1, 2, 3, 4, 5]

# Access
nums[0]  # 1

# Update
nums[0] = 10

# Append
nums.append(6)  # [1, 2, 3, 4, 5, 6]

# Insert
nums.insert(2, 99)  # [1, 2, 99, 3, 4, 5, 6]

# Remove by index
nums.pop(2)  # Removes 99

# Remove first occurrence
nums.remove(3)  # Removes first 3

# Check membership
if 4 in nums:
    print("Found")

# Find index
index = nums.index(4)

# Slicing
subarray = nums[1:4]  # [2, 3, 4]
reversed = nums[::-1]  # [5, 4, 3, 2, 1]

# Copy
copy = nums.copy()

# Sort
nums.sort()  # In-place
sorted_nums = sorted(nums)  # New list

# Filter
evens = [x for x in nums if x % 2 == 0]

String - Immutable

Strings in Python are immutable sequences of Unicode characters.

Common Operations

1. Access: string[index] - O(1)
2. Slicing: string[start:end:steps] - O(k)
3. Concatenation: string1 + string2 - O(n+m) - Creates new string
4. Join: string.join(list) - O(n) - Efficient for multiple strings
5. Find substring: substring in string - O(n)
6. Find index of substring: string.find(substring) - O(n)
7. Count occurrences: string.count(substring) - O(n)
8. Check prefix & suffix: string.startswith(substring) and string.endswith(substring) - O(k)
9. Replace substring: string.replace(old, new) - O(n)
10. Split: string.split(separator, maxsplit) - O(n)
11. Case conversion: .upper(), .lower(), .capitalize(), .title(), .swapcase() - O(n)
12. Strip whitespace: .strip(), .lstrip(), .rstrip() - O(n)
13. Character type checks: isdigit(), isalpha(), isalnum(), islower(), isupper(), isspace() - O(1)

Examples

s = "Hello World"

# Access
s[0]  # 'H'

# Slicing
s[1:5]  # "ello"
s[::-1]  # "dlroW olleH"

# Concatenation (inefficient in loops)
result = s + " Python"  # "Hello World Python"

# Join (efficient for multiple strings)
words = ["Hello", "World", "Python"]
result = " ".join(words)  # "Hello World Python"

# Find substring
if "World" in s:
    print("Found")

# Find index
index = s.find("World")  # 6

# Count
count = s.count("l")  # 3

# Prefix/Suffix
s.startswith("Hello")  # True
s.endswith("World")   # True

# Replace
new_s = s.replace("World", "Python")  # "Hello Python"

# Split
words = s.split()  # ["Hello", "World"]
words = s.split("l")  # ["He", "", "o Wor", "d"]

# Case conversion
s.upper()  # "HELLO WORLD"
s.lower()  # "hello world"
s.capitalize()  # "Hello world"
s.title()  # "Hello World"

# Strip
"  hello  ".strip()  # "hello"
"  hello  ".lstrip()  # "hello  "
"  hello  ".rstrip()  # "  hello"

# Type checks
"123".isdigit()  # True
"abc".isalpha()  # True
"abc123".isalnum()  # True
"HELLO".isupper()  # True

Dictionary

Dictionaries are hash tables providing O(1) average-case operations.

Common Operations

1. Insert/Update: dict["key"] = value - O(1)
2. Find value: dict["key"] or dict.get(key, default=None) - O(1)
3. Delete: del dict["key"] or dict.pop(key, default_value) - O(1)
4. Membership: key in dict - O(1)
5. Loop: dict.keys(), dict.values(), dict.items() - O(n) to iterate
6. Search for value: Iterate through values - O(n)
7. Remove all: dict.clear() - O(1)
8. Shallow copy: dict.copy() - O(n)
9. collections.defaultdict: Create non-existent keys without error handling, building frequency maps, adjacency lists
10. collections.Counter: Highly optimized for counting tasks

Examples

# Basic dictionary
d = {}
d["name"] = "John"
d["age"] = 30

# Access
name = d["name"]  # "John"
age = d.get("age", 0)  # Safe access

# Membership
if "name" in d:
    print("Key exists")

# Delete
del d["age"]
age = d.pop("age", 0)  # Returns default if not found

# Iterate
for key in d.keys():
    print(key)

for value in d.values():
    print(value)

for key, value in d.items():
    print(key, value)

# defaultdict - no KeyError for missing keys
from collections import defaultdict
dd = defaultdict(int)
dd["count"] += 1  # Automatically creates key with 0

# Counter - optimized counting
from collections import Counter
counter = Counter([1, 2, 2, 3, 3, 3])
print(counter)  # Counter({3: 3, 2: 2, 1: 1})
print(counter.most_common(2))  # [(3, 3), (2, 2)]

Sets

Sets are hash tables storing unique elements.

Common Operations

1. Add item: set.add(item) - O(1)
2. Remove item: set.remove(item) or set.pop() or set.discard(item) - O(1)
   • remove() raises KeyError if not found
   • discard() doesn’t throw error
3. Membership: item in set - O(1)
4. Union: set1 | set2 or set1.union(set2) - O(n+m)
5. Intersection: set1 & set2 or set1.intersection(set2) - O(min(n,m))
6. Difference: set1 - set2 or set1.difference(set2) - O(n)
7. Symmetric difference: set1 ^ set2 or set1.symmetric_difference(set2) - O(n+m)
8. Subset: set1.issubset(set2) or set1 <= set2 - O(n)
9. Superset: set1.issuperset(set2) or set1 >= set2 - O(m)
10. Proper subset/superset: set1 < set2 and set1 > set2 - O(n)

Examples

s = {1, 2, 3}

# Add
s.add(4)  # {1, 2, 3, 4}

# Remove
s.remove(4)  # Raises KeyError if not found
s.discard(4)  # No error if not found
s.pop()  # Removes arbitrary element

# Membership
if 2 in s:
    print("Found")

# Set operations
set1 = {1, 2, 3}
set2 = {3, 4, 5}

union = set1 | set2  # {1, 2, 3, 4, 5}
intersection = set1 & set2  # {3}
difference = set1 - set2  # {1, 2}
symmetric_diff = set1 ^ set2  # {1, 2, 4, 5}

# Subset/Superset
{1, 2}.issubset({1, 2, 3})  # True
{1, 2, 3}.issuperset({1, 2})  # True

Stack

Stacks are LIFO (Last In, First Out) data structures. In Python, use lists.

Common Operations

1. Push: stack.append(item) - O(1)
2. Pop: stack.pop() - O(1)
3. Peek: stack[-1] - O(1)
4. Is empty: not stack - O(1)
5. Loop: Iterate through array
6. Reverse: Use array reverse or pop and push every iteration

Examples

stack = []

# Push
stack.append(1)
stack.append(2)
stack.append(3)  # [1, 2, 3]

# Pop
top = stack.pop()  # 3, stack is now [1, 2]

# Peek
top = stack[-1]  # 2, doesn't remove

# Check empty
if not stack:
    print("Stack is empty")

Queue - collections.deque

Queues are FIFO (First In, First Out) data structures. Use collections.deque for efficient operations.

Common Operations

1. Enqueue: deque.append(item) - O(1)
2. Dequeue: deque.popleft() - O(1)
3. Peek at front: deque[0] - O(1)
4. Is empty: not deque - O(1)
5. Loop: for item in deque - O(n)

Examples

from collections import deque

queue = deque()

# Enqueue
queue.append(1)
queue.append(2)
queue.append(3)  # deque([1, 2, 3])

# Dequeue
front = queue.popleft()  # 1, queue is now deque([2, 3])

# Peek
front = queue[0]  # 2, doesn't remove

# Check empty
if not queue:
    print("Queue is empty")

# Also supports appendleft and pop for stack-like behavior
queue.appendleft(0)  # Add to front
queue.pop()  # Remove from back

Priority Queue - heapq

Priority queues use heaps. Python’s heapq implements a min-heap.

Common Operations

1. Insert: heapq.heappush(heaplist, item) - O(log n)
2. Pop: heapq.heappop(heaplist) - O(log n)
3. Peek: heaplist[0] - O(1)
4. Heapify: heapq.heapify(list) - O(n)
5. Push and pop (efficient): heapq.heappushpop(heap, item) - O(log n)
6. Pop then push: heapq.heapreplace(heap, item) - O(log n)
7. Get K smallest/largest: heapq.nsmallest(k, heaplist) and heapq.nlargest(k, heaplist) - O(n log k)

Examples

import heapq

# Create heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)  # [1, 2, 3] - min-heap

# Or heapify existing list
nums = [3, 1, 2]
heapq.heapify(nums)  # In-place, O(n)

# Pop smallest
smallest = heapq.heappop(heap)  # 1

# Peek
smallest = heap[0]  # 2, doesn't remove

# Push and pop
result = heapq.heappushpop(heap, 0)  # Pushes 0, pops 2

# Pop then push
result = heapq.heapreplace(heap, 5)  # Pops smallest, pushes 5

# Get k smallest/largest
smallest_3 = heapq.nsmallest(3, heap)  # [0, 2, 5]
largest_2 = heapq.nlargest(2, heap)  # [5, 2]

# Max-heap trick: Store negative values
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)  # [-3, -2, -1]
max_value = -heapq.heappop(max_heap)  # 3

Complete Time Complexity Table

Data Type	Operation / Method	Time Complexity (Avg)	Time Complexity (Worst)	Space Complexity	Common Use Case
list	append(x)	O(1) Amortized	O(N) (resize)	O(1)	Adding to end, stack implementation
	pop() (from end)	O(1) Amortized	O(N) (resize)	O(1)	Removing from end, stack
	insert(i, x)	O(N)	O(N)	O(1)	Inserting at specific index
	pop(i) (from index)	O(N)	O(N)	O(1)	Removing from specific index
	remove(x) (first occurrence)	O(N)	O(N)	O(1)	Searching and removing
	l[i] (access)	O(1)	O(1)	O(1)	Direct access by index
	l[i] = x (update)	O(1)	O(1)	O(1)	Direct update by index
	len(l)	O(1)	O(1)	O(1)	Getting size
	x in l (membership)	O(N)	O(N)	O(1)	Checking if element exists
	l.sort() (in-place)	O(N log N)	O(N log N)	O(log N) or O(N)	Sorting the list
	sorted(l) (returns new)	O(N log N)	O(N log N)	O(N)	Getting a sorted copy
	l.reverse() (in-place)	O(N)	O(N)	O(1)	Reversing the list
	l[:] or l.copy() (shallow)	O(N)	O(N)	O(N)	Creating a shallow copy
	Slicing l[a:b]	O(k) (k = b-a)	O(k)	O(k)	Creating sublists
str	s[i] (access)	O(1)	O(1)	O(1)	Accessing characters
	len(s)	O(1)	O(1)	O(1)	Getting length
	s1 + s2 (concatenation)	O(N+M)	O(N+M)	O(N+M)	Creates new string (inefficient in loops)
	"".join(iterable)	O(L) (L=total length)	O(L)	O(L)	Efficiently concatenating multiple strings
	Slicing s[a:b]	O(k) (k = b-a)	O(k)	O(k)	Creating substrings
	char in s (membership)	O(N)	O(N)	O(1)	Checking if character/substring exists
	s.find(sub) / s.index(sub)	O(N*M) (naive), O(N+M) (actual)	O(N*M)	O(1) or O(M)	Finding substring
	s.replace(old, new)	O(N)	O(N)	O(N)	Returns new string with replacements
	s.split(sep)	O(N)	O(N)	O(N)	Splitting string into a list
dict	d[key] (access)	O(1)	O(N) (hash collisions)	O(1)	Getting value by key
	d.get(key, default)	O(1)	O(N) (hash collisions)	O(1)	Safe access by key
	d[key] = value (insert/update)	O(1)	O(N) (hash collisions)	O(1)	Storing key-value pairs
	del d[key] / d.pop(key)	O(1)	O(N) (hash collisions)	O(1)	Removing items
	key in d (membership)	O(1)	O(N) (hash collisions)	O(1)	Checking if key exists
	len(d)	O(1)	O(1)	O(1)	Getting number of key-value pairs
	d.keys(), d.values(), d.items()	O(1) for view obj, O(N) to iterate	O(1) for view obj, O(N) to iterate	O(1) (view obj)	Iterating over keys, values, or items
set	add(x)	O(1)	O(N) (hash collisions)	O(1)	Adding unique elements
	remove(x)	O(1)	O(N) (hash collisions)	O(1)	Removing element (raises KeyError if not found)
	discard(x)	O(1)	O(N) (hash collisions)	O(1)	Safe removal of element
	pop() (arbitrary element)	O(1)	O(N) (hash collisions)	O(1)	Remove and return an arbitrary element
	x in s (membership)	O(1)	O(N) (hash collisions)	O(1)	Fast check for element existence
	len(s)	O(1)	O(1)	O(1)	Getting number of unique elements
	Set operations (&, |, -, ^)	O(len(s1)+len(s2)) (approx)	O(len(s1)*len(s2)) (worst case)	O(len(s1)+len(s2))	Union, intersection, difference, symmetric difference
collections.deque	append(x)	O(1)	O(1)	O(1)	Adding to right end
	appendleft(x)	O(1)	O(1)	O(1)	Adding to left end (core for BFS queues)
	pop() (from right)	O(1)	O(1)	O(1)	Removing from right end
	popleft() (from left)	O(1)	O(1)	O(1)	Removing from left end (core for BFS queues)
	d[i] (access, not recommended)	O(N)	O(N)	O(1)	Possible but slow, deques are not for random access
	rotate(n)	O(N)	O(N)	O(1)	Rotating elements
collections.Counter	(Inherits from dict)	(Like dict)	(Like dict)	(Like dict)	Specialized dictionary for counting
	c[key] += 1	O(1)	O(N) (hash collisions)	O(1)	Incrementing counts
	most_common(n)	O(K log k_mc) (K items, k_mc=n)	O(K log k_mc)	O(k_mc)	Getting n most common elements
collections.defaultdict	(Inherits from dict)	(Like dict)	(Like dict)	(Like dict)	Dictionary with default values
	d[non_existent_key]	O(1) (for factory call)	O(N) (hash collisions)	O(1) (+ space for new value)	Accessing a key calls default_factory if key missing
heapq module	heapq.heappush(heap, item)	O(log N)	O(log N)	O(1)	Adding item to heap (min-heap by default)
	heapq.heappop(heap)	O(log N)	O(log N)	O(1)	Removing smallest item from heap
	heapq.heapify(list)	O(N)	O(N)	O(1) (in-place)	Transforming a list into a heap in-place
	heap[0] (access min/max)	O(1)	O(1)	O(1)	Accessing smallest element (for min-heap)
	heapq.nlargest(k, iter)	O(N log k)	O(N log k)	O(k)	Get k largest elements
	heapq.nsmallest(k, iter)	O(N log k)	O(N log k)	O(k)	Get k smallest elements
tuple	t[i] (access)	O(1)	O(1)	O(1)	Immutable sequence, fast access
	len(t)	O(1)	O(1)	O(1)	Getting size
	x in t (membership)	O(N)	O(N)	O(1)	Checking if element exists (linear scan)
	Slicing t[a:b]	O(k) (k = b-a)	O(k)	O(k)	Creating subtuples (used as dict keys if elements are hashable)

Key Takeaways

1. Lists: Use for stacks, but insert() and remove() are O(n) - avoid in performance-critical code
2. Strings: Immutable - use join() instead of + in loops
3. Dictionaries: O(1) average-case operations - perfect for lookups, frequency counting, memoization
4. Sets: O(1) membership testing - ideal for duplicate detection and visited tracking
5. Deque: O(1) operations on both ends - use for queues and BFS
6. Heapq: O(log n) insert/pop - use for priority queues and finding k largest/smallest elements
7. Counter: Optimized for counting - use for frequency maps
8. Defaultdict: No KeyError handling needed - use for grouping and adjacency lists

Common Patterns

Frequency Counting

from collections import Counter

nums = [1, 2, 2, 3, 3, 3]
counter = Counter(nums)
# Or manually
freq = {}
for num in nums:
    freq[num] = freq.get(num, 0) + 1

Adjacency List

from collections import defaultdict

graph = defaultdict(list)
graph[1].append(2)
graph[1].append(3)

Two Sum Pattern

# O(n) using dictionary
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Sliding Window with Set

# Longest substring without repeating characters
def longest_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

---

This reference guide should help you make informed decisions about which data structures to use in your algorithms and coding interviews. Remember: choosing the right data structure can make the difference between an O(n²) and O(n) solution!