Level 2. Sorting and Searching

Classic techniques that appear in almost every contest problem: sorting, two pointers, prefix sums, and binary search.

The four techniques of this level are the workhorses of every olympiad: sorting as a tool, two pointers, prefix sums and binary search. Almost every entry-level "aha" problem is solved by one of them or their combination. The readiness criterion for level 3: you recognize these techniques in unfamiliar problems — "a sorted array and pairs" hints at two pointers, "many sum queries" at prefixes, "the minimum X for which it is possible" at binary search on the answer.

In this section

  1. 1
    Sorting Algorithms

    Sorting as a tool: std::sort, comparators, sorting structs.

  2. 2
    Two Pointers

    The two pointers technique: pairs with a given sum and a sliding window in O(n).

    1 problems

  3. 3
    Prefix Sums

    Prefix sums: answering "sum on a segment" in O(1); the difference array.

    1 problems

  4. 4
    Binary Search

    Binary search over an array and over the answer: O(log n), invariants and typical mistakes.

Доска