1. Big-O Complexity Cheat Sheet

Helper libraries in Python

• collections.deque → O(1) pops/appends at both ends.
• collections.Counter → Fast frequency counting.
• collections.defaultdict → Cleaner hash maps with default values.
• heapq → Priority queue implementation.
• bisect → Binary search on sorted arrays.

2. Strings & Arrays

Common Patterns

• Two pointers: Used for palindromes, merging sorted arrays, sliding windows.
• Sliding window: Substring/array problems (longest substring, max sum subarray).
• Prefix sums: Range queries, subarray sums.
• Hash maps (dict): Fast lookup for duplicates, anagrams, substrings.

Practice Problems

1. Reverse a string → O(n).
2. Check palindrome (ignore punctuation, spaces).
3. Longest substring without repeating characters (sliding window).
4. Two Sum (hash map, O(n)).
5. Maximum subarray (Kadane’s algorithm, O(n)).

Compare Core Data Structures | Operation | List | Dict | Set | Queue/Deque | | —————– | ————— | ————————– | ————– | ——————— | | len() | ✅ | ✅ | ✅ | ✅ | | in (membership) | O(n) | O(1) | O(1) | O(n) | | pop() | End only (O(1)) | By key (O(1) avg) | Arbitrary O(1) | Left/right O(1) | | clear() | ✅ | ✅ | ✅ | ✅ | | sorted() | ✅ | On .items() (O(n log n)) | ✅ | Convert to list first | | Iteration | for x in list | for k,v in dict.items() | for x in set | for x in deque |

Arrays & Lists (Python Focus)

Key Properties

Common Operations

Example Snippets

Iterating

nums = [1, 2, 3, 4]
for x in nums:
    print(x)

Adding & Removing

nums.append(5)       # [1,2,3,4,5]
nums.insert(2, 10)   # [1,2,10,3,4,5]
nums.remove(3)       # removes first '3'
popped = nums.pop()  # removes last element, returns it

Sorting

nums.sort()          # ascending
nums.sort(reverse=True)  # descending
sorted_copy = sorted(nums)  # returns new list

Pseudocode (for clarity)

function insert(list, index, value):
    shift elements right from index
    place value at index

Dictionaries (Python dict)

Key Properties

• Key-value store (hash table under the hood).
• Keys must be hashable (immutable types: str, int, tuple).
• Average-case operations: O(1) lookup, insert, delete.
• Worst-case O(n) (rare, due to hash collisions).

Common Operations

Special Methods

• .keys() → view of all keys (iterable).
• .values() → view of all values.
• .items() → iterable of (key, value) tuples.
• .update({...}) → bulk add/update.
• .popitem() → remove last inserted (Python ≥ 3.7 keeps insertion order).

Example Snippets

Iteration

d = {"a": 1, "b": 2, "c": 3}

for k in d:                # keys
    print(k)

for v in d.values():       # values
    print(v)

for k, v in d.items():     # key-value pairs
    print(k, v)

Adding & Removing

d["d"] = 4            # add
d.update({"e": 5})    # bulk add/update
del d["a"]            # delete
d.pop("b", None)      # delete with default

Sorting

# sort by key
print(sorted(d.items()))    # [('c', 3), ('d', 4), ('e', 5)]

# sort by value
print(sorted(d.items(), key=lambda x: x[1]))

Sets (set in Python)

Key Properties

• Unordered, unique elements only.
• Backed by hash table → O(1) avg lookup/insert/delete.
• No duplicates, no indexing.

Common Operations

Special Methods

• .update(iterable) → bulk add.
• .issubset(), .issuperset().
• .symmetric_difference().

Examples

s = {1, 2, 3}
s.add(4)             # {1,2,3,4}
s.remove(2)          # {1,3,4}
print(3 in s)        # True
print(s.union({5}))  # {1,3,4,5}

Stacks (LIFO)

Key Properties

• Last In, First Out (LIFO).
• Implement with list or collections.deque.

Common Operations

Example

stack = []
stack.append(1)
stack.append(2)
top = stack.pop()  # 2

Queues (FIFO)

Key Properties

• First In, First Out (FIFO).
• Use collections.deque for O(1) operations.

Common Operations

Example

from collections import deque
q = deque([1, 2])
q.append(3)        # [1,2,3]
front = q.popleft() # 1

Heaps / Priority Queues (heapq)

Key Properties

• Min-heap by default in Python.
• O(log n) insert/remove, O(1) peek min.
• Useful for scheduling, Dijkstra’s shortest path, top-K problems.

Common Operations

Example

import heapq
heap = [3, 1, 4]
heapq.heapify(heap)
heapq.heappush(heap, 2)
print(heapq.heappop(heap)) # 1