Back to Study Material Python

DSA Libraries

The collections module is the primary standard library source for specialised data structures. Key classes: Counter (frequency counting), deque (double-end...

DSA Libraries

collections Module

The collections module is the primary standard library source for specialised data structures. Key classes: Counter (frequency counting), deque (double-ended queue), OrderedDict (insertion-ordered dict with extra methods), defaultdict (dict with automatic default values), namedtuple (tuple with named fields), and ChainMap (link multiple dicts into one view). Mastering collections gives you efficient, readable solutions to many common DSA problems without writing data structures from scratch.

heapq Module

The heapq module implements a binary min-heap on top of a Python list. Key functions: heappush, heappop, heapify, nlargest, nsmallest. It is the standard tool for priority queues in Python. Used in Dijkstra's shortest path, Prim's MST, the k-th largest element problem, and merge-k-sorted-lists. Remember: heapq is a min-heap; negate values to simulate max-heap behaviour. heapify converts an existing list in O(n) time.

bisect Module

The bisect module provides binary search functions for sorted lists. bisect_left(a, x) returns the leftmost index where x can be inserted to keep a sorted. bisect_right(a, x) returns the rightmost such index. insort_left(a, x) and insort_right(a, x) insert x into the list maintaining sort order. These are O(log n) for the search but O(n) overall because list insertion shifts elements. Use sortedcontainers.SortedList (third-party) for O(log n) insertion and search.

itertools Module

itertools provides fast, memory-efficient tools for working with iterators and implementing common algorithmic patterns. Key functions: chain() concatenates iterables; combinations() and permutations() generate combinatorial sequences; product() gives the Cartesian product; groupby() groups consecutive elements; accumulate() computes running totals; islice() slices an iterator; cycle() repeats an iterable indefinitely. These functions avoid the need to write custom loops for common patterns and run at C speed internally.

functools Module

functools provides higher-order function utilities. lru_cache (and its alias cache in Python 3.9+) adds memoization to any function with a simple decorator. reduce() performs left-fold operations. partial() creates new functions with some arguments pre-filled: double = partial(pow, 2) pre-fills the base, but note the argument order. total_ordering allows you to define just __eq__ and __lt__ on a class and get all six comparison operators. cmp_to_key converts old-style comparison functions to key functions for sorted().

Exam Tip

Common library exam questions: what module provides deque? collections. What module provides binary search? bisect. What module provides lru_cache? functools. What module provides chain, product, and combinations? itertools. For coding interviews, the most impactful libraries to know deeply are collections (especially Counter, deque, defaultdict), heapq, and bisect. Mentioning the correct module when asked to solve a problem signals genuine Python knowledge rather than just algorithmic knowledge.