This chapter is a focused crash course on the Python features you will use repeatedly while learning 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.

Before we get into the language itself, let us address something practical. 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 import deserves special mention right away:

Python's default recursion limit is 1000. For DFS on a graph with 100,000 nodes or a skewed binary tree, you will hit a RecursionError without this line. We will cover recursion in detail later, but keep this in the back of your mind.

There is also one third-party library available on LeetCode that acts as Python's equivalent of Java's TreeMap and TreeSet:

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, you will use a small set of types over and over:

Now here is the single biggest advantage Python has over Java and C++ for DSA: Python integers have arbitrary precision. There is no overflow. Ever.

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 is a critical distinction that catches many candidates:

That last line is important. In Java, -7 / 2 gives -3 (truncates toward zero). In Python, -7 // 2 gives -4 (floors toward negative infinity). If you need truncation toward zero like Java, use int(-7 / 2) or math.trunc(-7 / 2).

The Ternary Expression

Python's equivalent of Java's condition ? valueIfTrue : valueIfFalse:

Multiple Assignment and Swap

One of Python's most elegant features 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 you will see them 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 actually more useful for DSA than Java's behavior:

This means you do not need the ((n % m) + m) % m trick that Java requires for positive modulo results.

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

Bitwise Operators

Bitwise operations unlock an entire category of problems:

The key bitwise operators you will encounter:

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 (>>> in Java). 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:

`enumerate()` is your best friend. Whenever you find yourself writing for i in range(len(nums)) just to access both the index and value, use enumerate() instead. It is cleaner, more Pythonic, and less error-prone:

Short-Circuit Evaluation

Python uses and and or (not && and || like Java):

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, you will frequently extract logic into helper functions. 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 incredibly convenient for DSA. It avoids passing extra parameters through recursive calls.

Pass-by-Object-Reference

A critical concept to understand: Python passes everything by object reference. This means:

This distinction matters enormously 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:

Notice the path[:] when saving results. 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 one of the most common bugs in backtracking solutions.

The Mutable Default Argument Pitfall

This is a Python-specific trap that catches even experienced developers:

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 most fundamental data structure in Python and the starting point for almost every DSA problem.

The 2D Array Trap

This is one of the most common Python bugs in interviews:

The [[0] * cols] * rows bug is one of the most common Python mistakes in interviews. 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. If an interviewer sees this bug, it signals unfamiliarity with 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 biggest advantages 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 one of the most common patterns you will write in matrix problems:

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

Notice how clean the Python version is compared to Java. Tuple unpacking with for dr, dc in directions and the chained comparison 0 <= nr < rows are both more readable than their Java equivalents.

Strings in Python are immutable. Every time you "modify" a string, Python creates a new object. This has a critical 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 deserves special attention. Since 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

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

This is one less thing to worry about compared to Java.

Useful String Patterns

This is the most important section of this chapter. Python's built-in dictionaries and sets, combined with the collections module, provide the data structures you will reach for in virtually 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 the Python equivalent of Java's HashMap. It provides O(1) average-case lookups, inserts, and deletes. Since Python 3.7, dictionaries maintain insertion order.

Key operations:

A critical 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. This is the Python equivalent of Java's NullPointerException when unboxing a null map.get() result.

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 incredibly powerful for DSA:

set -- Hash Set

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

The fact that add() does not raise an error when the element already exists means you can use it to detect duplicates by checking membership first:

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 essential for LRU cache implementations:

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

This concept is critical 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

Java has no built-in Pair or Tuple class, forcing you to use int[] arrays or custom classes. Python has tuples, and they are one of the language's biggest advantages for DSA.

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 incredibly 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. It is essential 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. 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.

Java has TreeMap and TreeSet built into the standard library. Python does not have a built-in sorted container, but it provides two alternatives: the bisect module for binary search on sorted lists, and the third-party sortedcontainers library (available on LeetCode).

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 O(log n) sorted data structures that are Python's equivalent of Java's TreeMap, TreeSet, and sorted list:

Comparison with Java TreeMap/TreeSet operations:

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 for multi-key sorting is very powerful. 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. These are not just stylistic preferences. They can significantly reduce the number of lines you write in an interview, leaving you 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 particularly powerful for sliding window problems:

map() and filter()

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

This is one of Python's biggest advantages for coding interviews. The @cache and @lru_cache decorators turn any recursive function into a memoized solution with zero boilerplate. Many DP problems that require 20+ lines of bottom-up tabulation in Java can be solved with a decorated recursive function in Python.

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 right tool:

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 simple but essential:

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) -- The Standard Approach

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):

Python does not throw Java's ConcurrentModificationException, but modifying a dictionary or set during iteration causes a RuntimeError. Modifying a list during iteration causes silent bugs.

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 significantly slower than Java and C++. While this rarely causes issues on LeetCode (time limits are adjusted per language), understanding performance pitfalls helps you avoid unnecessary TLE (Time Limit Exceeded) verdicts.

Common Performance Pitfalls

Tips for Avoiding TLE in Python