kartikkukreja

template <typename T>
class QueueWithMin {
private:
    queue<T> Q;
    deque<T> D;
public:
    void enqueue(T& x) {
        Q.push(x);
        while (!D.empty() && D.back() > x)
            D.pop_back();

kartikkukreja

template <typename T>
class QueueWithMin {
private:
    stack< pair<T, T> > S1, S2;
public:
    void enqueue(T& x) {
        S2.push(pair<T, T>(x, S2.empty() ? x : min(x, S2.top().second)));
    }

    T dequeue() {

kartikkukreja

template <typename T>
class QueueWithTwoStacks {
private:
    stack<T> S1, S2;
public:
    void enqueue(T& x) {
        S2.push(x);
    }

    T dequeue() {

kartikkukreja

template <typename T>
class StackWithMin {
private:
    stack< pair<T, T> > S;
public:
    void push(T& x) {
        S.push(pair<T, T>(x, S.empty() ? x : min(x, S.top().second)));
    }

    T pop() {

kartikkukreja

int factorial(int n) {
    if (n > 12) return INT_MAX;
    int f = 1;
    for (int i = 2; i <= n; i++)
        f *= i;
    return f;
}

void getPermutationHelper(vector<int>& num, int k, stringstream& ss) {
    if (num.size() == 0) return;

kartikkukreja

int factorial(int n) {
    if (n > 12) return INT_MAX;
    int f = 1;
    for (int i = 2; i <= n; i++)
        f *= i;
    return f;
}

string getPermutation(int n, int k) {
    k--; // 0-based indexing

kartikkukreja

int largestRectangleArea(vector<int> &A) {
    A.push_back(0); // sentinel to ensure all indices get popped off the stack
    stack<int> S;
    int maxArea = 0;
    for (int i = 0; i < A.size(); i++) {
        while (!S.empty() && A[S.top()] >= A[i]) {
            int height = A[S.top()];
            S.pop();
            int left = S.empty() ? 0 : S.top() + 1, right = i - 1;
            maxArea = max(maxArea, (right - left + 1) * height);

kartikkukreja

int largestRectangleArea(vector<int> &A) {
    int n = A.size();
    vector<int> posLeft(n);
    stack<int> S;
    for (int i = 0; i < n; i++) {
        while (!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posLeft[i] = S.empty() ? 0 : S.top() + 1;
        S.push(i);
    }

kartikkukreja

int largestRectangleArea(vector<int> &A) {
    int maxArea = 0;
    for (int i = 0; i < A.size(); i++) {
        for (int j = i, mn = A[i]; j < A.size(); j++) {
            mn = min(mn, A[j]);
            maxArea = max(maxArea, (j-i+1) * mn);
        }
    }
    return maxArea;
}

kartikkukreja

int largestRectangleArea(vector<int> &A) {
    int n = A.size();
    vector<int> posRight(n);
    stack<int> S;
    for (int i = n-1; i >= 0; i--) {
        while (!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posRight[i] = S.empty() ? n-1 : S.top() - 1;
        S.push(i);
    }