Misc Algorithms

Use standard-library algorithms when their contract fits the task because their implementations optimize for the target platform.

Nearest Smaller Element to the Left #

Maintain increasing values on the stack. Each index is pushed and popped once, giving \(O(n)\) time and \(O(n)\) space.

cpp

#include <cstddef>
#include <vector>

std::vector<int> nearest_left_smaller(const std::vector<int>& values) {
    std::vector<int> result(values.size(), -1);
    std::vector<std::size_t> stack;
    stack.reserve(values.size());

    for (std::size_t index = 0; index < values.size(); ++index) {
        while (!stack.empty() && values[stack.back()] >= values[index]) {
            stack.pop_back();
        }
        if (!stack.empty()) {
            result[index] = static_cast<int>(stack.back());
        }
        stack.push_back(index);
    }
    return result;
}

Use > instead of >= when an equal predecessor is valid. Reversing the scan or comparison produces next-greater, stock-span, histogram, and temperature-query variants.

Disjoint-Set Union #

Union by size and path halving give \(O(\alpha(n))\) amortized find and unite. A negative entry stores the root’s component size.

cpp

#include <utility>
#include <vector>

class DisjointSet {
public:
    explicit DisjointSet(int count) : parent_or_size_(count, -1) {}

    int find(int value) {
        while (parent_or_size_[value] >= 0) {
            const int parent = parent_or_size_[value];
            if (parent_or_size_[parent] >= 0) {
                parent_or_size_[value] = parent_or_size_[parent];
            }
            value = parent;
        }
        return value;
    }

    bool unite(int left, int right) {
        left = find(left);
        right = find(right);
        if (left == right) {
            return false;
        }
        if (parent_or_size_[left] > parent_or_size_[right]) {
            std::swap(left, right);
        }
        parent_or_size_[left] += parent_or_size_[right];
        parent_or_size_[right] = left;
        return true;
    }

private:
    std::vector<int> parent_or_size_;
};

unite returns false when both values already share a component. Values must be in [0, count).

Binary Heaps and Heapsort #

Heap construction is \(O(n)\); each push or pop is \(O(\log n)\).

cpp

#include <algorithm>
#include <vector>

void heapsort(std::vector<int>& values) {
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());
}

std::sort_heap produces ascending order in-place. Heapsort has \(O(n \log n)\) worst-case time and \(O(1)\) auxiliary storage, but std::sort is the better general-purpose sort.

Merge Sort and Inversion Counting #

Use std::stable_sort when equal elements must retain their input order. Merge sort costs \(O(n \log n)\) time and \(O(n)\) auxiliary storage.

cpp

#include <algorithm>
#include <vector>

template <class T, class Compare>
void stable_sort_records(std::vector<T>& values, Compare compare) {
    std::stable_sort(values.begin(), values.end(), compare);
}

For inversion counts, merge two sorted ranges and add the number of unmerged left elements whenever the right element is emitted. The resulting algorithm remains \(O(n \log n)\).

Prime Sieves #

Euler’s sieve records the least prime factor of every composite. Each composite is marked once, giving \(O(n)\) time and \(O(n)\) memory.

cpp

#include <vector>

std::vector<int> least_prime_factors(int limit) {
    std::vector<int> least_prime(limit + 1);
    std::vector<int> primes;

    for (int value = 2; value <= limit; ++value) {
        if (least_prime[value] == 0) {
            least_prime[value] = value;
            primes.push_back(value);
        }
        for (int prime : primes) {
            if (prime > limit / value) {
                break;
            }
            least_prime[prime * value] = prime;
            if (prime == least_prime[value]) {
                break;
            }
        }
    }
    return least_prime;
}

The division guard prevents overflow. Use Eratosthenes for a Boolean primality table and a segmented sieve when the complete range does not fit in memory.

Quickselect and Quicksort #

Use introspective standard-library algorithms because they avoid quicksort’s quadratic worst case and select without sorting the full range.

cpp

#include <algorithm>
#include <cstddef>
#include <vector>

void sort_values(std::vector<int>& values) {
    std::sort(values.begin(), values.end());
}

int select_nth(std::vector<int>& values, std::size_t rank) {
    std::nth_element(values.begin(), values.begin() + rank, values.end());
    return values[rank];
}

std::sort has \(O(n \log n)\) comparisons. std::nth_element has \(O(n)\) average complexity; rank must be less than values.size(), and neither resulting partition is sorted.