This chapter is a focused crash course on the Python features that come up repeatedly in DSA and preparing for coding interviews. Instead of covering the entire language, we will concentrate only on the parts that matter for solving problems efficiently in interviews.

On LeetCode, most imports are available automatically. But when writing Python locally or on some interview platforms, you need to know what to import. Here are the imports that cover 95% of DSA problems:

Each of these modules serves a specific purpose in DSA:

One line is worth adding up front:

Python's default recursion limit is 1000. Without this line, DFS on a graph with 100,000 nodes or a skewed binary tree raises a RecursionError. We will cover recursion in detail later.

There is also one third-party library available on LeetCode that provides sorted container data structures:

This is not part of Python's standard library, but it is available on LeetCode and many interview platforms. We will cover it in the Sorted Containers section.

Python is a dynamically typed language. You do not declare types, you just assign values. The interpreter figures out the type at runtime:

For DSA, a small set of types covers most problems:

Python integers have arbitrary precision, which is a big advantage for DSA. Python integers never overflow.

This means you never need to worry about integer overflow in most DSA problems. The safe binary search midpoint formula left + (right - left) // 2 is still good practice for clarity and habit, but technically unnecessary in Python because (left + right) // 2 will never overflow.

Floor Division vs True Division

This distinction matters:

That last line is important. In Python, -7 // 2 gives -4 because floor division rounds toward negative infinity, not toward zero. If you need truncation toward zero, use int(-7 / 2) or math.trunc(-7 / 2).

The Ternary Expression

Python writes conditional expressions inline using if/else:

Multiple Assignment and Swap

Python supports multiple assignment, which is handy for DSA:

The swap trick is particularly useful in partition-based algorithms and two-pointer problems where you constantly need to swap elements.

Type Hints

Python supports optional type hints that make your code clearer on LeetCode:

Type hints have no runtime effect. They are purely for readability. LeetCode uses them in function signatures, so they appear throughout this course.

Booleans Are Integers

A quirk worth knowing: bool is a subclass of int in Python. True is 1 and False is 0:

This is useful for counting conditions:

Most operators in Python work as you would expect, but a few deserve special attention for DSA.

Modular Arithmetic

The % operator in Python always returns a result with the same sign as the divisor (the right operand). This is convenient for DSA:

This means you do not need the ((n % m) + m) % m trick to force a positive modulo result.

Many problems ask you to return the result "modulo 10^9 + 7":

Bitwise Operators

Bitwise operations come up in several DSA patterns:

Key bitwise operators:

A common bit manipulation pattern is checking and setting individual bits, which shows up in problems using bitmasks to represent subsets:

Python also provides helpful built-in functions for bit operations:

Python does not have an unsigned right shift operator. Since Python integers have arbitrary precision, there is no fixed bit width, so unsigned shift does not apply. For problems that specifically require unsigned right shift behavior (like reversing bits of a 32-bit integer), you need to mask with & 0xFFFFFFFF to simulate 32-bit unsigned behavior.

Control Flow

Python offers several loop forms. Use each where it fits:

Use enumerate() for index-value pairs. When you need both the index and the value, use enumerate() instead of for i in range(len(nums)). It is cleaner and less error-prone:

Short-Circuit Evaluation

Python uses the keywords and and or for boolean logic:

Python's or has a useful idiom for default values:

Be careful with this pattern when 0 or "" are valid values. In those cases, use x if x is not None else default.

The Walrus Operator :=

Introduced in Python 3.8, the walrus operator assigns and returns a value in a single expression. It can make some DSA patterns more concise:

You do not need to use the walrus operator in interviews, but knowing it exists helps you read others' solutions.

In DSA problems, extracting logic into helper functions keeps the code clean. On LeetCode, your solution lives inside a class:

You can also define nested functions, which is common for DFS/backtracking:

Nested functions can access variables from the enclosing scope (like results and nums above). This is called a closure and it is convenient for DSA. It avoids passing extra parameters through recursive calls.

Pass-by-Object-Reference

Python passes everything by object reference. This means:

This distinction matters in recursive and backtracking problems. When you pass a list to a recursive call and add elements to it, those additions are visible to the caller. That is why the backtracking pattern works, adding and removing from a shared list as you explore different branches:

The path[:] when saving results creates a copy. If you wrote results.append(path) instead, every entry in results would be a reference to the same list, and they would all end up empty after backtracking unwinds. This is a common bug in backtracking solutions.

The Mutable Default Argument Pitfall

This is a Python-specific trap to watch for:

Modifying Integers in Nested Functions

If you need a nested function to modify an integer from the enclosing scope, you need the nonlocal keyword:

Without nonlocal, count += 1 would create a local variable instead of modifying the outer one. Alternatively, you can use a mutable container like a list [0] to avoid nonlocal, but that is less readable.

Lists are the foundational data structure in Python and the starting point for almost every DSA problem.

The 2D Array Trap

Watch for this pattern:

The [[0] * cols] * rows pattern is a Python-specific gotcha. Each row is a reference to the same list, so modifying one row modifies all of them. Always use a list comprehension for 2D arrays. This bug indicates a misunderstanding of Python's reference semantics.

Key List Operations

Negative Indexing

Python's negative indexing is one of its most useful features for DSA:

This comes up constantly. Peeking at the top of a stack? stack[-1]. Getting the last character of a string? s[-1]. Accessing the last row of a matrix? matrix[-1].

Slicing

Slicing creates a new list from a portion of an existing one. The syntax is lst[start:stop:step], where start is inclusive and stop is exclusive:

Slicing is particularly useful for:

Be aware that slicing creates a new list, so it costs O(k) time and space where k is the slice size. Do not slice inside a tight loop if you can avoid it.

List Comprehensions

List comprehensions are one of Python's most useful features for writing concise DSA code:

2D Arrays and the Directions Pattern

2D arrays appear in every matrix problem (BFS on grid, DP tables, etc.):

For DP problems, you often need a table with one extra row and column for the base case:

The 4-directional neighbor pattern is common in matrix problems:

For 8-directional movement (including diagonals), add the four diagonal pairs: (-1,-1), (-1,1), (1,-1), (1,1).

Tuple unpacking with for dr, dc in directions and the chained comparison 0 <= nr < rows make grid traversal code compact and readable.

Strings in Python are immutable. Every time you "modify" a string, Python creates a new object. This has a performance implication for DSA:

Essential String Methods

Character Arithmetic with ord() and chr()

Python does not have a separate char type. Characters are just strings of length 1. To do arithmetic on characters (which is common in DSA), use ord() and chr():

The ord(c) - ord('a') pattern works because characters have numeric values. Subtracting ord('a') from a lowercase letter gives its zero-based position. This is how you build frequency arrays without a dictionary:

This is faster and more memory-efficient than Counter(s) when you know the character set is limited to lowercase (or uppercase, or digits). However, for most interview problems, Counter is perfectly acceptable and more readable.

String Comparison

Python's == operator compares string content, not references:

Use == for string equality. The is operator checks object identity, which is rarely what you want for strings.

Useful String Patterns

Python's built-in dictionaries and sets, combined with the collections module, provide the data structures used in nearly every DSA problem. Choosing the right collection is often the difference between an O(n) and an O(n^2) solution.

dict: Hash Map

dict is Python's built-in hash map. It provides O(1) average-case lookups, inserts, and deletes. Since Python 3.7, dictionaries maintain insertion order.

Key operations:

A safety point: d[key] raises KeyError if the key does not exist. Always use d.get(key, default) for safe access, or check key in d first. Forgetting this guard is a common source of bugs in interview code.

defaultdict: Auto-Default Values

defaultdict from the collections module automatically creates a default value when you access a missing key. This eliminates the "check if key exists, create if not" pattern:

Compare this to the verbose alternative:

Common default factories:

Counter: Purpose-Built Frequency Counting

Counter from collections is the most concise way to count frequencies:

Counter arithmetic is useful for DSA:

set: Hash Set

set provides O(1) average-case membership testing:

Unlike some languages, set.add() returns nothing, so you detect duplicates by checking membership before adding:

Set operations are useful for certain DSA problems:

OrderedDict

Since Python 3.7, regular dict maintains insertion order. OrderedDict from collections is still useful for one specific operation: move_to_end(), which is used in LRU cache implementations:

Hashability: What Can Be a Dict Key or Set Element?

Hashability matters for Python DSA. Only hashable objects can be dict keys or set elements. The rule is simple: mutable objects are not hashable, immutable objects are.

This comes up constantly in DSA:

Collections Quick Reference

Python tuples are immutable, fixed-size sequences. They are the standard way to group a small number of related values, and they simplify many DSA patterns: coordinates, edges, intervals, and heap entries.

Why Tuples Matter for DSA

1. Tuples are hashable (unlike lists), so they can be dict keys and set elements:

2. Tuples compare lexicographically, which is useful for heap operations:

This means you can push tuples onto a heap and they will be ordered by the first element, with ties broken by the second element, and so on:

3. Tuple unpacking makes code cleaner:

deque (double-ended queue) from collections provides O(1) operations at both ends. Use it for BFS, sliding window problems, and monotonic deque patterns.

BFS Template

Every BFS implementation starts with a deque:

For level-order BFS (where you need to process all nodes at the current level before moving to the next), capture the queue size:

deque Operations

Monotonic Deque Pattern

The monotonic deque is used in "sliding window maximum/minimum" problems:

Bounded deque

You can create a deque with a maximum size. When full, adding to one end automatically removes from the other:

Python's heapq module provides heap operations on a regular list. The heap is always a min-heap, meaning the smallest element is always at index 0.

Basic Operations

The Max-Heap Trick

Python only provides a min-heap. To get a max-heap, negate the values:

This works because negating reverses the ordering: if a < b, then -a > -b.

Tuples in Heaps

Since tuples compare lexicographically, you can push tuples to sort by multiple fields. The first element of the tuple determines the primary sort order:

Caution with tuples: If the first elements are equal, Python compares the second elements. If the second elements are not comparable (e.g., custom objects without __lt__), you get a TypeError. Always include a tie-breaking field (like an index or counter) as the second element:

heapq Utility Functions

One important limitation: heapq does not support efficient removal of arbitrary elements. Removing a specific element that is not at the root requires an O(n) scan, and there is no remove method. If you need to invalidate heap elements, use lazy deletion: mark elements as deleted and skip them when they surface via heappop(). Alternatively, use SortedList from sortedcontainers which supports O(log n) removal.

Python does not ship a balanced binary search tree in its standard library, but it offers two ways to work with sorted data: the bisect module for binary search on sorted lists, and the third-party sortedcontainers library (available on LeetCode) for O(log n) sorted maps and sets.

bisect: Binary Search on Sorted Lists

The bisect module performs binary search to find insertion points in a sorted list:

The difference between bisect_left and bisect_right matters when the value exists in the list:

This makes bisect_left useful for "find the first element >= target" and bisect_right for "find the first element > target":

Insert while maintaining sort order:

Note that insort is O(log n) for the search but O(n) for the insertion (because shifting elements in a list is O(n)). For large lists with frequent insertions, use SortedList instead.

SortedList, SortedDict, SortedSet

The sortedcontainers library provides three O(log n) sorted data structures: SortedList, SortedDict, and SortedSet.

Common neighbor queries on a SortedList:

Sorting is a prerequisite for many algorithms: binary search, two pointers on sorted arrays, merge intervals, and greedy approaches.

Custom Sorting with key=

The key parameter takes a function that extracts a comparison key from each element. This is how you sort by custom criteria:

The tuple trick handles multi-key sorting cleanly. Python compares tuples lexicographically, so (len(w), w) sorts by length first, then alphabetically for words of the same length.

To sort one key ascending and another descending, negate the ascending key (for numbers) or reverse the sort:

cmp_to_key: When key= Is Not Enough

For rare problems where the comparison logic cannot be expressed as a simple key extraction, use cmp_to_key:

Sort Stability

Python's sort is stable (it uses TimSort). Elements that compare equal retain their relative order from the original list. This is useful for multi-key sorting. You can sort by secondary key first, then by primary key, and the secondary order is preserved within groups of equal primary keys:

Python offers several patterns that make DSA code more concise and readable. They reduce the number of lines you write in an interview, leaving more time for the actual algorithm.

List Comprehensions and Generator Expressions

List comprehensions create lists in a single expression:

Generator expressions are like list comprehensions but lazy. They do not create the entire list in memory:

zip(): Parallel Iteration

zip() pairs up elements from multiple iterables:

reversed(): Reverse Without Copying

reversed() returns an iterator that traverses in reverse. Unlike lst[::-1], it does not create a new list:

Multiple Assignment and Unpacking

Counter Arithmetic in Sliding Window

This pattern is useful for sliding window problems:

map() and filter()

While list comprehensions are generally preferred, map() can be useful for type conversions:

The @cache and @lru_cache decorators turn any recursive function into a memoized solution with zero boilerplate. Many DP problems that would normally require a manual memo dictionary or a full bottom-up table can be solved with a decorated recursive function.

Basic Usage

@cache is shorthand for @lru_cache(maxsize=None), introduced in Python 3.9. Both cache all results indefinitely.

2D DP Example

Using @cache on LeetCode

On LeetCode, your solution is a class method. Here is how to use @cache inside a class:

The nested function approach works cleanly because coins is captured from the enclosing scope and does not need to be a parameter (which would affect the cache key).

Key Constraints

Arguments must be hashable. You cannot pass lists to a cached function. Convert them to tuples:

Remember to clear the cache if you run multiple test cases and the cached function uses external state. On LeetCode, this is rarely needed because each test case creates a new Solution instance. But in local testing:

When to Use Manual Memo Instead

Sometimes @cache is not the best fit:

Use manual memo when:

Every function call in Python goes on the call stack. Python's default recursion limit is 1000, which is extremely low for DSA problems:

The fix is one line:

When to Worry About Stack Depth

Converting Recursion to Iteration

When recursion depth is proportional to input size and the input can be large, convert to iteration using an explicit stack:

Note that Python does not optimize tail recursion. Unlike some functional languages, a tail-recursive function in Python still adds a frame to the call stack on every call.

Graphs appear in a large portion of DSA problems. Python does not have a built-in graph class, so you need to build representations yourself. There are two common approaches.

Approach 1: defaultdict(list)

Use when node IDs can be anything (integers, strings, etc.):

Approach 2: List of Lists (when nodes are 0 to n-1)

More memory-efficient when node IDs are contiguous integers:

Weighted Graphs

Store tuples of (neighbor, weight):

Modifying a dictionary or set while iterating over it causes a RuntimeError. Modifying a list during iteration does not raise an error, but it causes silent bugs as indices shift underneath you.

Dictionaries and Sets

The same applies to sets:

Lists

Modifying a list while iterating does not raise an error, but it causes subtle bugs because indices shift:

In practice, most DSA problems do not require removing during iteration. You are far more likely to build a new collection with the desired elements.

Many DSA problems require avoiding duplicate results (e.g., 3Sum, 4Sum, permutations with duplicates). Python offers two approaches.

Sort and Skip Duplicates

This is the preferred approach for sorted array problems:

This runs in O(1) extra space (beyond the sort) and produces results in sorted order.

Set-Based Deduplication

Use a set to collect unique results. Remember that lists are not hashable, so convert to tuples:

The sort-and-skip approach is generally preferred in interviews because it avoids the overhead of hashing and produces cleaner code. But set-based deduplication is simpler to implement and is a valid fallback when the sort-and-skip logic is complex.

This section collects the small patterns and utilities that come up repeatedly across many problem types.

Sentinel Values

Math Utilities

Ceiling Division Without Importing math

Deep Copy vs Shallow Copy

Type Conversions

Infinity and Comparison Tricks

Many DSA problems use custom node classes. LeetCode typically defines these for you, but you should know the patterns:

Common Node Definitions

Custom Comparison for Heaps

If you need to put custom objects in a heap, define __lt__ (less than):

Alternatively, use a tuple with a counter as a tie-breaker (as shown in the heapq section). The tuple approach is generally preferred because it does not require modifying the class definition.

Python is one of the slower languages used in competitive programming. LeetCode adjusts time limits per language, so this rarely matters in practice, but understanding common performance pitfalls helps you avoid unnecessary TLE (Time Limit Exceeded) verdicts.

Common Performance Pitfalls

Tips for Avoiding TLE in Python