Python's DSA Toolkit and Its Hidden Costs

Big-O & the Python Toolkit, lesson 2 of 3

Python's DSA Toolkit and Its Hidden Costs

Know what each built-in really costs and reach for deque, set, heapq, bisect and Counter.

14 min, 0 of 5 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Python lets one short line hide a whole loop. These all take O(n) time on a list of length n:

  • x in nums, nums.index(x), nums.count(x)
  • min(nums), max(nums), sum(nums)
  • nums.pop(0) and nums.insert(0, x) (every other element shifts over)
  • copying a full list slice, or concatenating lists with n total items (a slice of k items takes O(k), even if the source is much bigger)

Repeating an O(n) call for each of n items makes your solution O(n²). Spotting that is a useful interview habit. We treat bounded-size integer comparisons and hashes as O(1); long strings and huge integers add their own costs.

Example

`in`: list vs set

A list scans element by element; a set hashes the value and jumps straight to it (O(1) on average). Build the set once, before the loop: if q in set(data) inside the loop rebuilds it every time and is even slower.

Example

Queues: list.pop(0) vs deque.popleft()

Any time you take things off the front (BFS, queues, sliding windows, simulations), use collections.deque. It has append, appendleft, pop and popleft, all O(1). Indexing into the middle of a deque is O(n), though.

Quiz

Which of these is O(1)?

Copies you didn't ask for.

  • nums[1:] creates a new list. A recursive function that passes nums[1:] each call does n + (n−1) + … copies: O(n²). Pass an index instead.
  • Strings are immutable, so s += piece in a loop can copy the whole string each time. (CPython sometimes optimises this, but don't count on it.) Collect pieces in a list and "".join(pieces) once at the end.
Quiz

What's the time complexity of total(nums)?

The toolkit. These are available on every problem in this course without importing:

  • Counter(items): counts in O(n); .most_common(k) for the top k.
  • defaultdict(list): group things without "if key not in d" boilerplate.
  • deque: O(1) at both ends.
  • heapq: a min-heap on a plain list. push and pop are O(log n), heap[0] is the minimum.
  • bisect: binary search on a sorted list in O(log n).
  • sorted(items, key=...): O(n log n), stable.
Example

Counter and a grouping template, traced

Counting and grouping are the two most common jobs for a hash map. Both take O(n) expected time for n bounded-size items; storing k distinct keys needs O(k) space. Grouping also stores the n grouped items. Follow the trace: hi creates bucket 2, cat creates bucket 3, and go extends bucket 2. Remove the trace print in a solution: printing growing lists adds extra work.

Example

heapq and bisect

heappop always returns the smallest item. bisect_left finds the first index whose value is ≥ x, bisect_right the first index whose value is > x; either can return len(scores). Both assume the list is sorted. Searching is O(log n), but bisect.insort takes O(n): inserting into a list still shifts items.

Example

Sorting with a key

The key function runs once per element, then Python compares the keys. Return a tuple to sort by several fields, and negate a number to flip one field to descending. Expensive keys add their own cost. sorted returns a new list; items.sort() changes the list and returns None. Both may use O(n) temporary space.

Quiz

What does this print?

Quiz

What does this print?

Exercise

Spot the hidden loop

count_allowed(queries, allowed) returns how many items in queries also appear in allowed. The starter version is correct, but q in allowed scans the whole list for every query: O(q × a).

Make it O(q + a) by converting allowed to a set once, before the loop. The check spies on the list to make sure it is no longer searched with in.