Search, selection, and ordered state.

These patterns retain only candidates that can still affect the answer. Binary search keeps a boundary containing the first feasible value. A size-k heap keeps only the best k elements seen so far. A monotonic stack removes values once a nearer, stronger boundary makes them irrelevant.

Boundary binary search

Memorize a boundary invariant rather than several loop variants. For lower bound, [0, low) is known to be less than the target, while [high, n) is known to be at least the target. [low, high) remains unknown. Assigning high = middle keeps middle as a possible answer. Assigning low = middle + 1 discards it.

lower_bound_index.cppstd::size_t lower_bound_index(
    std::span<const int> values,
    int target
) {
    std::size_t low = 0;
    std::size_t high = values.size();
    while (low < high) {
        const std::size_t middle = low + (high - low) / 2;
        if (values[middle] < target) low = middle + 1;
        else high = middle;
    }
    return low;
}

Upper bound changes the comparison to values[middle] <= target, producing the first value greater than the target. The count of target occurrences is upper_bound - lower_bound. Use the standard algorithms in production code. Implement the loop when the predicate or virtual search space is custom.

Binary search on the answer

The input itself need not be sorted. The answer space is ordered: capacities below a threshold fail, and every larger capacity succeeds. Establish safe bounds first. For shipping, one day must hold the heaviest package, and one day can hold the total weight.

ship_within_days.cppint ship_within_days(std::span<const int> weights, int days) {
    int low = *std::max_element(weights.begin(), weights.end());
    int high = std::accumulate(weights.begin(), weights.end(), 0);

    const auto feasible = [&](int capacity) {
        int used_days = 1;
        int load = 0;
        for (const int weight : weights) {
            if (load + weight > capacity) {
                ++used_days;
                load = 0;
            }
            load += weight;
        }
        return used_days <= days;
    };

    while (low < high) {
        const int middle = low + (high - low) / 2;
        if (feasible(middle)) high = middle;
        else low = middle + 1;
    }
    return low;
}

The complexity is the feasibility cost multiplied by the logarithm of the answer range. State the units: shipping uses O(n log(sum(weights))). For floating-point answers, run a fixed number of iterations or stop when the interval is below a stated tolerance. Do not test floating-point endpoints for exact equality.

Heap and top-k

For the k largest values, keep a min-heap of size k. Its top is the weakest retained candidate and therefore the one to evict. After processing any prefix, the heap contains the k largest values in that prefix.

top_k_largest.cppstd::vector<int> top_k_largest(
    std::span<const int> values,
    std::size_t count
) {
    std::priority_queue<int, std::vector<int>, std::greater<>> keep;
    for (const int value : values) {
        keep.push(value);
        if (keep.size() > count) keep.pop();
    }

    std::vector<int> answer;
    while (!keep.empty()) {
        answer.push_back(keep.top());
        keep.pop();
    }
    return answer; // ascending among the retained values
}

Merge K Sorted Lists stores one current node from each list in a min-heap, so heap size is k rather than the total number of nodes. Task schedulers often combine a heap ordered by priority with a queue ordered by next eligibility time. Top K Frequent can use a heap over frequency entries or frequency buckets for linear time.

Two heaps for a running median

Split the stream into a max-heap holding the lower half and a min-heap holding the upper half. Every lower value must be no greater than every upper value, and the lower heap has either the same size or one extra element. The median is the lower top or the average of both tops.

running_median.cppclass RunningMedian {
public:
    void push(int value) {
        if (lower_.empty() || value <= lower_.top()) lower_.push(value);
        else upper_.push(value);

        if (lower_.size() > upper_.size() + 1) {
            upper_.push(lower_.top());
            lower_.pop();
        } else if (upper_.size() > lower_.size()) {
            lower_.push(upper_.top());
            upper_.pop();
        }
    }

    double median() const {
        if (lower_.size() == upper_.size())
            return (static_cast<double>(lower_.top()) + upper_.top()) / 2.0;
        return lower_.top();
    }

private:
    std::priority_queue<int> lower_;
    std::priority_queue<int, std::vector<int>, std::greater<>> upper_;
};

Sliding Window Median also needs deletion. C++ offers multiset iterators for direct erasure, or two heaps can use lazy-deletion maps and prune invalid tops. A Fenwick tree of frequencies is another option after coordinate compression.

Quickselect

Partition moves one pivot into its final sorted position. Only the side containing the desired rank remains relevant, unlike quicksort, which recurses into both sides. Randomized or shuffled pivots give expected linear time. Consistently poor pivots give quadratic worst-case time.

quickselect.cppint kth_smallest(std::vector<int> values, std::size_t rank) {
    std::size_t left = 0;
    std::size_t right = values.size(); // [left, right)

    while (true) {
        const int pivot = values[right - 1];
        std::size_t boundary = left;
        for (std::size_t i = left; i + 1 < right; ++i)
            if (values[i] < pivot)
                std::swap(values[i], values[boundary++]);
        std::swap(values[boundary], values[right - 1]);

        if (boundary == rank) return values[boundary];
        if (rank < boundary) right = boundary;
        else left = boundary + 1;
    }
}

C++ already provides std::nth_element, which rearranges the range so the nth element matches the fully sorted value and every element before it compares no greater. Use it unless implementing the partition is itself the subject.

Monotonic stack

Store indices, not only values, when the answer needs distance or width. In Daily Temperatures, unresolved indices remain in decreasing temperature order. A warmer current day resolves every colder index on top. Each index is pushed once and popped at most once.

daily_temperatures.cppstd::vector<int> daily_temperatures(
    std::span<const int> temperatures
) {
    std::vector<int> wait(temperatures.size(), 0);
    std::vector<std::size_t> decreasing;

    for (std::size_t day = 0; day < temperatures.size(); ++day) {
        while (!decreasing.empty() &&
               temperatures[decreasing.back()] < temperatures[day]) {
            const std::size_t previous = decreasing.back();
            decreasing.pop_back();
            wait[previous] = static_cast<int>(day - previous);
        }
        decreasing.push_back(day);
    }
    return wait;
}

Largest Rectangle in Histogram pops when a shorter bar arrives. The popped bar’s right boundary is the current index and its left boundary is one after the new stack top. A sentinel zero height at the end flushes remaining bars through the same logic.

Monotonic deque

The front is the best live index. Remove it when it expires. Before appending the new index, remove weaker values from the back because the new value is at least as good and expires later.

sliding_window_max.cppstd::vector<int> sliding_window_max(
    std::span<const int> values,
    std::size_t width
) {
    if (width == 0 || width > values.size()) return {};
    std::deque<std::size_t> candidates;
    std::vector<int> answer;

    for (std::size_t right = 0; right < values.size(); ++right) {
        while (!candidates.empty() &&
               candidates.front() + width <= right)
            candidates.pop_front();
        while (!candidates.empty() &&
               values[candidates.back()] <= values[right])
            candidates.pop_back();
        candidates.push_back(right);
        if (right + 1 >= width)
            answer.push_back(values[candidates.front()]);
    }
    return answer;
}

A deque works only when range endpoints move forward. Arbitrary range maximum queries require a segment tree or sparse table. DP transitions such as dp[i] = cost[i] + min(dp[j]) over a recent position window can use the same deque over DP values.

Trie

An array-backed lowercase trie stores child node indices rather than pointers. Index zero is the root. -1 is the missing-child sentinel. Appending to the node vector can reallocate it, so never hold a reference into nodes_ across push_back.

lowercase_trie.cppclass LowercaseTrie {
    struct Node {
        std::array<int, 26> child = [] {
            std::array<int, 26> value{};
            value.fill(-1);
            return value;
        }();
        bool terminal = false;
    };
    std::vector<Node> nodes_{1};

public:
    void insert(std::string_view word) {
        std::size_t node = 0;
        for (const char character : word) {
            const auto letter = static_cast<std::size_t>(character - 'a');
            int next = nodes_[node].child[letter];
            if (next == -1) {
                next = static_cast<int>(nodes_.size());
                nodes_[node].child[letter] = next; // assign before reallocation
                nodes_.push_back({});
            }
            node = static_cast<std::size_t>(next);
        }
        nodes_[node].terminal = true;
    }
};

A fixed 26-way node is fast but can waste memory on sparse alphabets. Use a sorted vector or hash map per node for Unicode or large alphabets. Word Search II combines a trie with board DFS: stop a board path as soon as the trie has no matching edge, and clear terminal markers after emitting a word to avoid duplicates.