Implementations C++ #include <cstddef> #include <vector> template <typename T, typename Cmp = std::less<T>> class Heap { private: std::vector<T> array_; Cmp comp_; // INFO: you don't need a size // INFO: it's complete b tree in the sense that you FILL the // r...
Implementations C++ #include <cstddef> template <typename T> class LinkedList { private: // INFO: only C needs struct Node like creation, in cpp can just do Node // so you never need that typedef thing struct Node { Node *next; Node *prev; T value; // copy ctors on T expected, fails othe...
Implementations C++ #include <concepts> #include <cstddef> #include <vector> template <typename Ops, typename S, typename L> concept LazySegConcept = requires(S a, S b, L f, L g, std::size_t len) { { Ops::identity_value() } -> std::same_as<S>; { Ops::combine(a, b) } ...
general ideas for what I notice and feel while solving a problem the solution is not the code, implementation is not the challenge here ( well not at this stage ).
Backtracking Core Idea Backtracking is controlled brute force: dfs(state): if state is complete: record answer return for choice in valid choices from state: choose dfs(next state) undo Common Shapes Pick Or Skip Use when every element has exactly two choices: take it or leave it.
Forward index Use this when recursion moves forward through an array or string.
Over a state Use this when recursion places something into a row, cell, grid path, bucket, or slot while constraints decide whether the choice is legal.
Permutations And Counts Use this when order matters. The recursion fills one position at a time by choosing from values that remain available.
Trick is often “verification” being easier vs finding the value. Monotonicity of course is needed ^ on the answer space.
K-th Order Find K-th Smallest Pair Distance Whenever you think of log squared → a sliding window is almost always possible.