All Nearest Smaller Values

The All Nearest Smaller Values (ANSV) problem requires computing, for each element in an input array, the index or value of the closest preceding element that is strictly smaller. Leveraging a monotonic stack invariant, optimal linear time complexity O(n) is achieved by maintaining a dynamically filtered history of candidate extrema, avoiding the naive O(n^2) nested-loop scan.

#include <vector>
#include <stack>
#include <cstdint>

std::vector<int32_t> compute_ansv(const std::vector<int32_t>& input) {
    const size_t n = input.size();
    std::vector<int32_t> result(n, -1); // Default to -1 if no smaller value exists
    std::stack<size_t> monotonic_stack;
    monotonic_stack.push(0);
    result[0] = -1;
    return result;
}

#include <vector>
#include <stack>
#include <cstdint>

std::vector<int32_t> compute_ansv(const std::vector<int32_t>& input) {
    size_t n = input.size();
    std::vector<int32_t> ansv(n);
    std::stack<size_t> st;

    for (size_t i = 0; i < n; ++i) {
        while (!st.empty() && input[st.top()] >= input[i]) {
            st.pop();
        }
        ansv[i] = st.empty() ? -1 : static_cast<int32_t>(st.top());
        st.push(i);
    }
    return ansv;
}

#include <cassert>
#include <vector>

void run_tests() {
    std::vector<int32_t> input = {4, 5, 2, 10, 8};
    std::vector<int32_t> expected = {-1, 0, -1, 2, 2};
    auto result = compute_ansv(input);
    assert(result == expected);
}

#include <vector>
#include <cstdint>

std::vector<int32_t> compute_ansv_optimized(const std::vector<int32_t>& input) {
    size_t n = input.size();
    std::vector<int32_t> ansv(n);
    std::vector<size_t> stack;
    stack.reserve(n);

    for (size_t i = 0; i < n; ++i) {
        while (!stack.empty() && input[stack.back()] >= input[i]) {
            stack.pop_back();
        }
        ansv[i] = stack.empty() ? -1 : static_cast<int32_t>(stack.back());
        stack.push_back(i);
    }
    return ansv;
}

Mathematical Formulation & Complexity Proof

Let A = [a_0, a_1, …, a_(n-1)] be an array of integers. The All Nearest Smaller Values problem seeks an array R of size n where R[i] = max({j | j < i and A[j] < A[i]}) union {-1 if no such j exists}. While a naive implementation evaluates all preceding indices resulting in O(n^2) worst-case performance, the monotonic stack approach guarantees O(n) time complexity. Each index is pushed onto the stack exactly once and popped at most once. Consequently, the total number of stack operations across the entire execution loop is bounded by 2n, yielding an amortized time complexity of O(1) per iteration and an overall time complexity of O(n).

Architectural Considerations & Memory Layout

In high-throughput distributed engines or real-time trading systems, cache invalidation dictates microarchitectural performance. Standard library containers like std::stack wrap std::deque by default, introducing non-contiguous memory allocations and pointer dereference penalties. Replacing the stack with a pre-allocated contiguous std::vector ensures sequential memory access patterns, allowing hardware prefetchers to load cache lines efficiently and reducing branch mispredictions during comparative bounds checks.

Common Failure Modes & Edge Cases

Developers frequently encounter out-of-bounds indexing or integer overflow when casting container sizes (size_t) to signed integers (int32_t). Explicit boundary casting and handling vectors with duplicate values are critical. When duplicate elements exist (A[j] == A[i]), the strict inequality condition (A[stack.back()] >= A[i]) ensures that plateaus are correctly bypassed, correctly identifying the preceding strictly smaller element rather than an equivalent neighbor.