84. Largest Rectangle in Histogram

Info

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

#include <functional>
#include <iostream>
#include <print>
#include <ranges>
#include <stack>
#include <vector>
 
namespace UsingStack {
    template<typename Compare>
    std::vector<int> computePreviousSmallerElement(std::ranges::constant_range auto&& arr, Compare&& cmp) {
        std::stack<int> stack;
        std::vector<int> prevElem;
        for (auto const& [idx, elem]: arr | std::views::enumerate) {
            while (!stack.empty() && cmp(elem, arr[stack.top()])) {
                stack.pop();
            }
            auto prevElemIdx = stack.empty() ? -1 : stack.top();
            prevElem.push_back(prevElemIdx);
            stack.push(idx);
        }
        return prevElem;
    }
}
 
namespace UsingJumpPointers {
    template<typename Compare>
    std::vector<int> computePreviousSmallerElement(std::ranges::constant_range auto&& arr, Compare&& cmp) {
        std::vector<int> prevElem;
        for (auto const& [idx, elem]: arr | std::views::enumerate) {
            auto prevElemIdx = idx - 1;
            while (prevElemIdx != -1  && cmp(elem, arr[prevElemIdx])) {
                prevElemIdx = prevElem[prevElemIdx];
            }
            prevElem.push_back(prevElemIdx);
        }
        return prevElem;
    }
}
 
int largestRectangleInHistogram(std::vector<int> const& arr) {
    using namespace UsingJumpPointers;
 
    auto leftSmallerElements = computePreviousSmallerElement(arr, std::less_equal<int>());
    auto rightSmallerElements = computePreviousSmallerElement(arr | std::views::reverse, std::less_equal<int>())
        | std::views::reverse
        | std::views::transform([size = static_cast<int>(arr.size())](auto const& reversedIdx) {
            return size - 1 - reversedIdx;
        })
        | std::ranges::to<std::vector>();
    
    int maxArea = 0;
    for (auto const& [idx, height]: arr | std::views::enumerate) {
        std::println("{} {} {}", leftSmallerElements[idx], idx, rightSmallerElements[idx]);
        auto width = rightSmallerElements[idx] - leftSmallerElements[idx] - 1;
        maxArea = std::max(maxArea, height * width);
    }
    return maxArea;
}
 
int main() {
    auto area = largestRectangleInHistogram({2, 1, 5, 6, 2, 3});
    std::println("largestRectangleInHistogram area: {}", area);
}

Time complexity of UsingJumpPointers is $\mathcal{O}(n)$

Intuition: In this part of the code,

while (prevElemIdx != -1  && cmp(elem, arr[prevElemIdx])) {
	prevElemIdx = prevElem[prevElemIdx];
}

Imagine that prevElemIdx disappears from the array after this while loop runs. Everything else would still work, and each element can disappear atmost once. So, time complexity must be $\mathcal{O}(n)$