Skip to content
Tutorials Center
My learning

Topics

Lesson 196 of 225 ยท Advanced Topics

Designing Data Structures

Learn to design custom data structures in Python: min-stack, O(1) randomized set, time-based key-value store, snapshot array and iterator design.

So far you have learned structures one at a time. Interviews and real software often ask the reverse: "Build something that supports these operations, each in O(1) (or O(log n))". Nobody hands you the structure; you have to combine the pieces you know, such as arrays, hash maps, stacks, heaps and binary search, so that each operation gets what it needs.

This kind of problem is called data structure design. The skill is a method more than a trick: write down the operations and their required speed, ask which structure is fast at each one alone, and then find the glue that lets them cooperate. In this lesson you will design five structures: a min-stack, a randomized set, a time-based key-value store, a snapshot array and an iterator.

A method for design problems

  1. List the operations and the target complexity of each.
  2. Find the conflict. For example, a hash set deletes in O(1) but cannot pick a random element; an array picks randomly in O(1) but deletes in O(n).
  3. Pair structures so that each covers the other's weakness, and keep them consistent (every operation must update both).
  4. Trade space for time where needed: an extra stack or map is usually cheap.
  5. Test the edge cases: empty structure, duplicates, repeated operations.

Design 1: a stack with get-min in O(1)

Problem. Support push, pop, top and get_min (the smallest value currently in the stack), all in O(1).

Brute force. Scan the stack for the minimum each time: get_min is O(n).

Better. The minimum at any moment depends only on which items are in the stack, and a stack only changes at the top. So store, next to each item, the minimum of everything below and including it. When you pop an item, its saved minimum disappears with it, and the one below becomes correct again.

TEXT
push 5   push 3   push 7   push 3
items:  [5]    [5,3]    [5,3,7]   [5,3,7,3]
mins:   [5]    [5,3]    [5,3,3]   [5,3,3,3]
get_min:  5      3        3         3
Python Min-stack: get_min in O(1)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four operations are O(1) and the structure needs O(n) space. A trick saves space by storing the minimum only when it changes, but the paired-stack version is the one you can get right under pressure.

Design 2: insert, delete, get-random in O(1)

Problem. Build a set with insert(x), remove(x) and get_random() (each element equally likely), all in average O(1).

Conflict. A Python set or dict does insert and remove in O(1) but cannot return a random element without converting to a list (O(n)). A list gives a random element in O(1) via a random index, but removing an arbitrary value is O(n): finding it takes O(n), and shifting the rest takes O(n) more.

Glue. Keep a list of the values and a dict mapping each value to its index in the list. To remove x, take its index i, copy the last element into slot i, update the moved element's index in the dict, and pop the last slot. The list stays packed, and removal costs O(1) because popping the end of a list is O(1).

TEXT
list:  [10, 20, 30, 40]     index: {10:0, 20:1, 30:2, 40:3}
remove 20:
  move last (40) into slot 1 -> [10, 40, 30, 40]
  pop last                   -> [10, 40, 30]
  index: {10:0, 40:1, 30:2}      (20 deleted, 40 updated)
Python Randomized set with O(1) remove

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The check if i < len(self._values) handles the case where x was the last element: then there is nothing to move, and moving would wrongly re-add the removed value to the index. This is the classic bug in this design.

Design 3: a time-based key-value store

Problem. set(key, value, timestamp) stores a value; get(key, timestamp) returns the value stored at the largest timestamp not greater than the query timestamp, or an empty string if there is none. Timestamps for a key arrive in increasing order.

Brute force. Store all (timestamp, value) pairs per key and scan them on get: O(n).

Better. Because timestamps arrive in increasing order, each key's list is already sorted. Use binary search (bisect_right) for the last entry at or before the query time: O(log n) per get, O(1) per set.

Python Time-based key-value store with bisect

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Keeping two parallel lists lets bisect work on plain integers. (You could also store tuples; the parallel lists avoid building a key function.)

Design 4: a snapshot array

Problem. An array of length n starting at all zeros. Support set(index, value), snap() (take a snapshot and return its id, starting at 0) and get(index, snap_id) (the value at that index when that snapshot was taken).

Brute force. Copy the whole array on every snap: O(n) time and memory per snapshot, which explodes for many snapshots.

Better. Record only changes. For each index keep a sorted list of (snap_id, value) entries. set writes the value for the current snapshot id (overwriting if the last entry already has it). snap just increments a counter: O(1). get binary-searches the index's history for the latest entry with snap_id <= requested.

Python Snapshot array storing only changes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

snap costs O(1), set costs O(1), and get costs O(log h), where h is the number of changes to that index. Memory grows with the number of set calls, not with the number of snapshots times the array size.

Design 5: an iterator

An iterator hands out the elements of a collection one at a time. Designing one means deciding what state to keep so next() and has_next() are cheap. A good example is flattening a list of lists: [[1, 2], [], [3], [4, 5]] should give 1, 2, 3, 4, 5 without building the flat list first (which would use O(total) memory up front).

The state is two numbers, the current inner list and the position inside it. has_next() skips over exhausted or empty lists until it finds an element, so empty inner lists never confuse the caller. In Python, an iterator is an object with __iter__ and __next__; a generator is the shortest way to write one.

Python A lazy flattening iterator, two ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same pattern, "advance past what is empty before answering", powers many iterator problems: peeking iterators, zig-zag iterators over several lists, and iterators over trees (where the state is an explicit stack).

Design 6: browser history

Support visit(url), back(steps) and forward(steps). The current page is always one item. Pages you can go back to form a stack; pages you can go forward to form a second stack. Moving back pops from the back stack and pushes the page you leave onto the forward stack, and moving forward does the opposite. Visiting a new page pushes the current page on the back stack and clears the forward stack, because the old forward path no longer exists.

Python Browser history with two stacks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each back or forward of k steps costs O(k), and visit is O(1) (amortized, because of the clear). If you need O(1) jumps for any number of steps, keep one array of pages and an index instead, and truncate the array on a visit. The stack version is the more natural one to explain in an interview.

Common mistakes

  • Forgetting to keep structures in sync. In the randomized set, updating the list but not the dict (or the reverse) silently breaks everything. Put both updates in one method and test removal of the last element.
  • Choosing the wrong complexity target. A design that is O(n) in one operation may be fine if that operation is rare, and wrong if it is the main one. Read the constraints.
  • Copying instead of recording changes. Snapshot-style problems almost always want change logs plus binary search.
  • Using list.pop(0) or list.remove(x) as "O(1)". They are O(n). Use collections.deque or swap with the last element.
  • Ignoring duplicates and empties. Ask what remove of a missing item, get of an unknown key and pop from an empty stack should do.

You will meet the same ideas in the LRU and LFU cache (hash map + linked list), the median of a stream (two heaps) and union-find (parent array with path compression). Each one is "two simple structures cooperating".

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the min-stack, what does the parallel stack store?

    Each saved value is the smallest item at or below that position. Popping removes the item and its saved minimum together, so the minimum below stays correct.
  2. 2. Why does the randomized set remove an element by copying the last element into its slot?

    Moving the last item into the hole and popping the end keeps the list packed without shifting elements. The dict maps values to indexes so the hole is found in O(1).
  3. 3. What is the time per get() in the time-based key-value store?

    The timestamps are sorted because they arrive in order, so bisect finds the last timestamp at or before the query in logarithmic time.
  4. 4. Why is a snapshot array better than copying the array on each snap()?

    Only changed cells are recorded, tagged with the snapshot id. Reads binary-search the cell's short history.
  5. 5. In the flatten iterator, why does has_next() skip empty inner lists?

    Positioning on a real element before answering means has_next() is accurate and next() always has a value to return.

Summary

  • Design problems combine known structures; start by listing operations and target complexities, then find the conflict and the glue.
  • Min-stack: a parallel stack of running minimums gives O(1) get_min.
  • Randomized set: a list plus a value-to-index dict gives O(1) insert, remove and random pick; remove swaps with the last element.
  • Time-based store and snapshot array: keep change logs sorted by time and answer reads with binary search.
  • Iterators keep a small state and advance lazily; generators with yield do it for you.

Next: P, NP and Hard Problems