Level 3. Data Structures and Greedy Algorithms

Stack, queue, sets and maps, recursion, greedy algorithms, and DSU — the toolkit for mid-level problems.

The toolbox level: stack and queue, set and map, recursive search, greedy algorithms and DSU. After it you will choose the data structure to fit the problem instead of bending the problem to fit an array. The readiness criterion for level 4: you can write DSU and backtracking search from memory, and for a greedy solution you can explain WHY it is correct.

In this section

  1. 1
    Stack and Queue

    The stack (LIFO) and the queue (FIFO): bracket sequences and processing order.

  2. 2
    Sets and Maps

    set and map: fast membership tests, counting distinct values and frequencies in O(log n).

  3. 3
    Recursion and Backtracking

    Recursion and exhaustive search: subsets, permutations and the tree of choices.

  4. 4
    Greedy Algorithms

    Greedy algorithms: the locally best step, the non-overlapping intervals problem, limits of applicability.

  5. 5
    Disjoint Set Union (DSU)

    Disjoint Set Union: find and union with path compression — almost O(1).

Доска