Stack and Queues¶

/*
Question:
Write a program to implement a Stack using Array. Your task is to use the class as shown in the comments in the code editor and complete the functions push() and pop() to implement a stack.

Approach:
- We use a class `MyStack` to represent the stack.
- The stack is implemented using an array `arr` and a top variable to keep track of the top element.
- The class provides two member functions: `push(int)` to push an element onto the stack and `pop()` to pop an element from the stack.
- The `push(int)` function increments the top and adds the element to the array at the current top index.
- The `pop()` function checks if the stack is empty (top = -1), in which case it returns -1. Otherwise, it retrieves the element at the top index, decrements the top, and returns the element.

Code:
*/

class MyStack
{
private:
    int arr[1000];
    int top;

public:
    MyStack() { top = -1; }
    int pop();
    void push(int);
};

void MyStack::push(int x)
{
    top++;
    arr[top] = x;
}

int MyStack::pop()
{
    if (top == -1) {
        return -1;
    }
    int ans = arr[top];
    top--;
    return ans;
}

/*
Complexity Analysis:
- The time complexity of both `push()` and `pop()` operations is O(1) since they involve constant-time operations like incrementing/decrementing the top and accessing/modifying the array elements.
- The space complexity is O(1) since the array has a fixed size and does not depend on the number of elements pushed into the stack.
*/

/*
Question:
Implement a Queue using an Array. Queries in the Queue are of the following type:
(i) 1 x   (a query of this type means pushing 'x' into the queue)
(ii) 2     (a query of this type means to pop an element from the queue and print the popped element)

Approach:
- We use a class `MyQueue` to represent the queue.
- The queue is implemented using an array `arr`, a front variable to keep track of the front element, and a rear variable to keep track of the next available position to insert an element.
- The class provides two member functions: `push(int)` to push an element into the queue and `pop()` to pop an element from the front of the queue.
- The `push(int)` function inserts the element at the rear index and increments the rear.
- The `pop()` function checks if the queue is empty (rear == front), in which case it returns -1. Otherwise, it retrieves the element at the front index, increments the front, and returns the element.

Code:
*/

class MyQueue {
private:
    int arr[100005];
    int front;
    int rear;

public:
    MyQueue() { front = 0; rear = 0; }
    void push(int);
    int pop();
};

void MyQueue::push(int x)
{
    arr[rear] = x;
    rear++;
}

int MyQueue::pop()
{
    if (rear == front)
        return -1;
    int ans = arr[front];
    front++;
    return ans;
}

/*
Complexity Analysis:
- The time complexity of both `push()` and `pop()` operations is O(1) since they involve constant-time operations like accessing/modifying array elements and incrementing/decrementing front/rear indices.
- The space complexity is O(N) where N is the maximum number of elements that can be stored in the queue (in this case, 100005) since we use an array to store the queue elements.
*/

/*
Question:
Implement a Stack using one queue.

Approach:
- We use the class `QueueStack` to represent the stack.
- The stack is implemented using one queue `q`.
- The `push(int)` function inserts an element into `q`.
- The `pop()` function transfers `n-1` elements from front of `q` to it's back and returns the last element from `q` as the popped element.


Code:
*/

class QueueStack {
private:
    std::queue<int> q;

public:
    void push(int x);
    int pop();
};

void QueueStack::push(int x)
{
    q.push(x);
}

int QueueStack::pop()
{
    if (q.empty())
        return -1;

    for(int i=0; i<q.size()-1; i++){
        int temp = q.front();
        q.pop();
        q.push(temp);
    }

    int popped = q.front();
    q.pop();

    return popped;
}


/*
Complexity Analysis:
- The `push()` operation has a time complexity of O(1) since we only need to enqueue an element into `q`.
- The `pop()` operation has a time complexity of O(N) in the worst case, where N is the number of elements in `q`.
- The space complexity is O(N), where N is the total number of elements stored in the queue.
*/

/*
Question:
Implement a Queue using two stacks s1 and s2.

Approach:
- We use the class `Queue` to represent the queue.
- The queue is implemented using two stacks `input` and `output`.
- The `enqueue(int)` function inserts an element into `input` stack.
- The `dequeue()` function transfers elements from `input` stack to `output` stack if `output` is empty, and returns the top element from `output` stack as the dequeued element.
- To transfer elements from `input` to `output`, we pop each element from the top of `input` and push it into `output`.
- After transferring elements, we pop the top element from `output` as the dequeued element.

Code:
*/

class Queue {
private:
    std::stack<int> input;
    std::stack<int> output;

public:
    void enqueue(int x);
    int dequeue();
};

void Queue::enqueue(int x) {
    input.push(x);
}

int Queue::dequeue() {
    if (input.empty() && output.empty())
        return -1;

    if (output.empty()) {
        while (!input.empty()) {
            int temp = input.top();
            input.pop();
            output.push(temp);
        }
    }

    int dequeued = output.top();
    output.pop();

    return dequeued;
}

/*
Complexity Analysis:
- The `enqueue()` operation has a time complexity of O(1) since we only need to push an element into the `input` stack.
- The `dequeue()` operation has a time complexity of O(1) by amortized analysis.
- The space complexity is O(N), where N is the total number of elements stored in the two stacks.
*/

/*
Question:
You have a linked list and you have to implement the functionalities push and pop of stack using this given linked list. Your task is to use the class as shown in the comments in the code editor and complete the functions push() and pop() to implement a stack.

Approach:
- We use the class `MyStack` to represent the stack implemented using a linked list.
- The stack is implemented using a singly linked list where each node represents an element in the stack.
- The `push(int)` function inserts an element at the top of the stack by creating a new node and updating the `next` pointer to point to the current top.
- The `pop()` function removes the top element from the stack by updating the `top` pointer to the next node and returning the data of the removed node.

Code:
*/

class MyStack {
private:
    struct StackNode {
        int data;
        StackNode* next;

        StackNode(int x) : data(x), next(NULL) {}
    };

    StackNode* top;

public:
    MyStack() : top(NULL) {}
    void push(int x);
    int pop();
};

void MyStack::push(int x) {
    StackNode* temp = new StackNode(x);
    temp->next = top;
    top = temp;
}

int MyStack::pop() {
    if (!top)
        return -1;

    int popped = top->data;
    StackNode* temp = top;
    top = top->next;

    return popped;
}

/*
Complexity Analysis:
- The `push()` operation has a time complexity of O(1) since we only need to create a new node and update the `top` pointer.
- The `pop()` operation has a time complexity of O(1) since we only need to update the `top` pointer and delete the node.
- The space complexity is O(N), where N is the total number of elements stored in the stack (linked list).
*/

/*
QUESTION:
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.

Example:
Input: s = "()"
Output: true

APPROACH:
- We can use a stack to keep track of the opening brackets.
- Whenever we encounter an opening bracket, we push it onto the stack.
- If we encounter a closing bracket, we check if it matches the top of the stack.
- If the closing bracket matches the top of the stack, we pop the top element from the stack.
- If at any point the closing bracket does not match the top of the stack or the stack is empty, the string is not valid.
- Finally, if the stack is empty after processing all characters, the string is valid.

CODE:
*/

bool isValid(string& s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } 
        else {
            if (st.empty())
                return false;

            char open = st.top();
            if ((open == '(' && c == ')') || (open == '[' && c == ']') || (open == '{' && c == '}')) {
                st.pop();
            } else {
                return false;
            }
        }
    }

    return st.empty();
}

/*
COMPLEXITY ANALYSIS:
- The code iterates through the input string once, so the time complexity is O(n), where n is the length of the input string.
- The space complexity is O(n) as we use a stack to store the opening brackets.
*/

/*
QUESTION:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class.
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

Example:
Input:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output:
[null,null,null,null,-3,null,0,-2]
Explanation:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

APPROACH:
- We can use an auxiliary stack to keep track of the difference of an element from the minimum element at each step.
- When pushing an element, we push the difference of an element from the minimum element at that time.
- When popping an element, we check stack top if it's -ve it means that this element is the minimum so we update the mini as we popping the current minimum.
- To get the top element, we add the current minimum to the top element of the main stack.
- To get the minimum element, we simply return the current minimum.

CODE:
*/

class MinStack {
private:
    stack<long long> st;
    int mini;
public:
    MinStack() {
        mini = -1;
    }

    void push(int val) {
        if (st.empty()) {
            st.push(0);
            mini = val;
        } else {
            st.push((long long)val - mini);// to handle overflow case
            mini = min(val, mini);
        }
    }

    void pop() {
        if (st.top() < 0)
            mini = mini - st.top();
        st.pop();
    }

    int top() {
        int ans = -1;
        if (st.top() < 0)
            ans = mini;
        else
            ans = mini + st.top();
        return ans;
    }

    int getMin() {
        return mini;
    }
};

/*
COMPLEXITY ANALYSIS:
- All the operations (push, pop, top, getMin) have O(1) time complexity as we are performing constant-time operations on the stack.
- The space complexity is O(n) as we use an auxiliary stack to store the minimum elements.
*/

/*
QUESTION:
Given an infix expression in the form of string str, convert it to a postfix expression.

Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -.

Example:
Input: str = "a+b*(c^d-e)^(f+g*h)-i"
Output: abcd^e-fgh*+^*+i-
Explanation:
After converting the infix expression into postfix expression, the resultant expression will be abcd^e-fgh*+^*+i-

APPROACH:
- We can use a stack to convert the infix expression to postfix.
- We iterate through each character of the input string.
- If the character is an operand (letter or digit), we append it to the output string.
- If the character is an opening parenthesis '(', we push it onto the stack.
- If the character is a closing parenthesis ')', we pop elements from the stack and append them to the output string until we encounter an opening parenthesis. We also discard the opening parenthesis from the stack.
- If the character is an operator, we compare its precedence with the top element of the stack. If the top element has higher precedence, we pop it and append it to the output string. We repeat this process until we find an operator with lower precedence or an opening parenthesis. Then we push the current operator onto the stack.
- After iterating through all characters, we pop any remaining elements from the stack and append them to the output string.

CODE:
*/

string infixToPostfix(string s) {
    string ans = "";
    unordered_map<char, int> precedence;
    precedence['^'] = 3;
    precedence['*'] = 2;
    precedence['/'] = 2;
    precedence['+'] = 1;
    precedence['-'] = 1;

    stack<char> st;

    for (int i = 0; i < s.size(); i++) {
        if (('a' <= s[i] && s[i] <= 'z') || ('A' <= s[i] && s[i] <= 'Z') || ('0' <= s[i] && s[i] <= '9')) {
            ans.push_back(s[i]);
        } else if (s[i] == '(') {
            st.push(s[i]);
        } else if (s[i] == ')') {
            while (!st.empty() && st.top() != '(') {
                ans.push_back(st.top());
                st.pop();
            }
            st.pop();
        } else {
            while (!st.empty() && st.top() != '(' && precedence[st.top()] >= precedence[s[i]]) {
                ans.push_back(st.top());
                st.pop();
            }
            st.push(s[i]);
        }
    }

    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the infixToPostfix function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operators.
*/

/*
QUESTION:
Given an infix expression in the form of string str. Convert this infix expression to postfix expression.

Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands.
Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -.

Example:
Input: str = "((A-(B/C))*((A/K)-L))"
Output: "*-A/BC-/AKL"
Explanation:
After converting the infix expression into prefix expression, the resultant expression will be *-A/BC-/AKL.

APPROACH:
- We can use a stack to convert the infix expression to postfix.
- We iterate through each character of the input string from right to left.
- If the character is an alphanumeric character, we append it to the output string.
- If the character is an closing parenthesis '(', we push it onto the stack.
- If the character is a opening parenthesis ')', we pop operators from the stack and append them to the output string until we encounter an closing parenthesis '('.
- If the character is an operator, we compare its precedence with the top of the stack and pop operators with higher or equal precedence and append them to the output string. Then we push the current operator onto the stack.
- After iterating through all characters, we pop any remaining operators from the stack and append them to the output string.

CODE:
*/

string infixToPostfix(string s) {
    string ans = "";
    unordered_map<char, int> precedence;
    precedence['^'] = 3;
    precedence['*'] = 2;
    precedence['/'] = 2;
    precedence['+'] = 1;
    precedence['-'] = 1;

    stack<char> st;

    for (int i = s.size() - 1; i >= 0; i--) {
        if (('a' <= s[i] && s[i] <= 'z') || ('A' <= s[i] && s[i] <= 'Z') || ('0' <= s[i] && s[i] <= '9')) {
            ans.push_back(s[i]);
        } else if (s[i] == ')') {
            st.push(s[i]);
        } else if (s[i] == '(') {
            while (!st.empty() && st.top() != ')') {
                ans.push_back(st.top());
                st.pop();
            }
            st.pop(); // Pop the closing parenthesis ')'
        } else {
            while (!st.empty() && st.top() != ')' && precedence[st.top()] >= precedence[s[i]]) {
                ans.push_back(st.top());
                st.pop();
            }
            st.push(s[i]);
        }
    }

    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    reverse(ans.begin(), ans.end());
    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the infixToPostfix function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operators.
*/

/*
QUESTION:
You are given a string S of size N that represents the prefix form of a valid mathematical expression. Convert it to its infix form.

Example:
Input: 
*-A/BC-/AKL
Output: 
((A-(B/C))*((A/K)-L))
Explanation: 
The above output is its valid infix form.

APPROACH:
- We can use a stack to convert the prefix expression to infix.
- We iterate through each character of the input string in reverse order.
- If the character is an operand (letter or digit), we push it onto the stack.
- If the character is an operator, we pop two operands from the stack, concatenate them with the operator and enclosing parentheses, and push the result back onto the stack.
- After iterating through all characters, the top of the stack will contain the final infix expression.

CODE:
*/

string preToInfix(string pre_exp) {
    stack<string> st;

    for (int i = pre_exp.size() - 1; i >= 0; i--) {
        char ch = pre_exp[i];

        if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9')) {
            string temp = "";
            temp += ch;
            st.push(temp);
        } else {
            string a = st.top();
            st.pop();
            string b = st.top();
            st.pop();

            string temp = "(" + a + ch + b + ")";
            st.push(temp);
        }
    }

    return st.top();
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the preToInfix function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operands.
*/

/*
QUESTION:
You are given a string that represents the prefix form of a valid mathematical expression. Convert it to its postfix form.

Example:
Input: 
*-A/BC-/AKL
Output: 
ABC/-AK/L-*
Explanation: 
The above output is its valid postfix form.

APPROACH:
- We can use a stack to convert the prefix expression to postfix.
- We iterate through each character of the input string in reverse order.
- If the character is an alphanumeric character, we push it onto the stack.
- If the character is an operator, we pop two operands from the stack, concatenate them with the operator, and push the result back onto the stack.
- After iterating through all characters, the top of the stack will contain the final postfix expression.

CODE:
*/

bool isAlphaNumeric(char ch) {
    return ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9');
}

string preToPost(string pre_exp) {
    stack<string> st;

    for (int i = pre_exp.size() - 1; i >= 0; i--) {
        char ch = pre_exp[i];

        if (isAlphaNumeric(ch)) {
            string temp = "";
            temp += ch;
            st.push(temp);
        } else {
            string a = st.top();
            st.pop();
            string b = st.top();
            st.pop();

            string temp = a + b + ch;
            st.push(temp);
        }
    }

    return st.top();
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the preToPost function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operands.
*/

/*
QUESTION:
You are given a string that represents the postfix form of a valid mathematical expression. Convert it to its infix form.

Example:
Input:
ab*c+ 
Output: 
((a*b)+c)
Explanation: 
The above output is its valid infix form.

APPROACH:
- We can use a stack to convert the postfix expression to infix.
- We iterate through each character of the input string.
- If the character is an alphanumeric character, we push it onto the stack.
- If the character is an operator, we pop two operands from the stack, concatenate them with the operator in the proper order (operand1 + operator + operand2), and push the result back onto the stack.
- After iterating through all characters, the top of the stack will contain the final infix expression.

CODE:
*/

bool isAlphaNumeric(char ch) {
    return ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9');
}

string postToInfix(string exp) {
    stack<string> st;

    for (int i = 0; i < exp.size(); i++) {
        char ch = exp[i];

        if (isAlphaNumeric(ch)) {
            string temp = "";
            temp += ch;
            st.push(temp);
        } else {
            string a = st.top();
            st.pop();
            string b = st.top();
            st.pop();

            st.push("(" + b + ch + a + ")");
        }
    }

    return st.top();
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the postToInfix function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operands.
*/

/*
QUESTION:
You are given a string that represents the postfix form of a valid mathematical expression. Convert it to its prefix form.

Example:
Input: 
ABC/-AK/L-*
Output: 
*-A/BC-/AKL
Explanation: 
The above output is its valid prefix form.

APPROACH:
- We can use a stack to convert the postfix expression to prefix.
- We iterate through each character of the input string.
- If the character is an alphanumeric character, we push it onto the stack.
- If the character is an operator, we pop two operands from the stack, concatenate them with the operator in the proper order (operator + operand2 + operand1), and push the result back onto the stack.
- After iterating through all characters, the top of the stack will contain the final prefix expression.

CODE:
*/

bool isAlphaNumeric(char ch) {
    return ('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z') || ('0' <= ch && ch <= '9');
}

string postToPre(string post_exp) {
    stack<string> st;

    for (int i = 0; i < post_exp.size(); i++) {
        char ch = post_exp[i];

        if (isAlphaNumeric(ch)) {
            string temp = "";
            temp += ch;
            st.push(temp);
        } else {
            string a = st.top();
            st.pop();
            string b = st.top();
            st.pop();

            string temp = ch + b + a;
            st.push(temp);
        }
    }

    return st.top();
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the postToPre function is O(N), where N is the length of the input string.
- We iterate through each character once, and the operations performed inside the loop are all constant time.
- The space complexity is O(N) as we use a stack to store operands.
*/

/*
Question:
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Approach:
- We can solve this problem using a stack and a hashmap.
- First, we iterate through the `nums2` array from right to left.
- For each element, we pop elements from the stack that are smaller than or equal to the current element and store the next greater element for each popped element in the hashmap.
- Finally, we iterate through the `nums1` array and retrieve the next greater element from the hashmap if it exists, otherwise assign -1.

Code:
*/

void nextGstack(vector<int>& nums, unordered_map<int, int>& mp) {
    stack<int> st;
    for (int i = nums.size() - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= nums[i]) {
            st.pop();
        }
        if (!st.empty())
            mp[nums[i]] = st.top();

        st.push(nums[i]);
    }
}

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> mp;
    nextGstack(nums2, mp);

    vector<int> ans(nums1.size(), -1);

    for (int i = 0; i < nums1.size(); i++) {
        if (mp.find(nums1[i]) != mp.end())
            ans[i] = mp[nums1[i]];
    }
    return ans;
}

/*
Complexity Analysis:
- The time complexity of the `nextGreaterElement` function is O(N + M), where N is the size of `nums1` and M is the size of `nums2`.
- The `nextGstack` function has a time complexity of O(M), where M is the size of `nums2`.
- The space complexity is O(N), where N is the size of `nums1`, to store the result in the `ans` vector and the `mp` hashmap.
*/

/*QUESTION:
Given a circular integer array `nums` (i.e., the next element of `nums[nums.length - 1]` is `nums[0]`), return the next greater number for every element in `nums`.

The next greater number of a number `x` is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, return -1 for this number.

Example:

Input: `nums = [1,2,1]`
Output: `[2,-1,2]`
Explanation: The first 1's next greater number is 2. The number 2 doesn't have a next greater number. The second 1's next greater number needs to be searched circularly, which is also 2.

APPROACH:
To find the next greater number for each element in a circular array, we can utilize a stack. 
We iterate through the array in reverse order to handle the circular nature of the array. 
For each element, we compare it with the elements in the stack. 
If an element in the stack is smaller than or equal to the current element, we pop it from the stack since it cannot be the next greater number.
The top of the stack at each iteration will hold the next greater element for the corresponding element in the array.

CODE:*/

// NOTE:- we could also implement this via two for loops from n-1 to 0, instead of a single loop of 2*n to 0; cause the complexity remains the same

vector<int> nextGreaterElements(vector<int>& nums) {
    vector<int> ans(nums.size(), -1);
    stack<int> st;

    for (int i = 2 * nums.size() - 1; i >= 0; i--) {
        while (!st.empty() && nums[st.top()] <= nums[i % nums.size()])
            st.pop();

        if (!st.empty())
            ans[i % nums.size()] = nums[st.top()];

        st.push(i % nums.size());
    }

    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(N), where N is the size of the input array `nums`. We iterate through the array twice: once to find the next greater element in the first pass and once to handle the circular nature of the array in the second pass.
- The space complexity is O(N) as we use a stack to store the indices of elements.
*/

/*QUESTION:
Given an array `a` of integers of length `n`, find the nearest smaller number for every element such that the smaller element is on the left side. If no smaller element is present on the left, print -1.

Example:

Input: n = 3
a = {1, 6, 2}
Output: -1 1 1
Explanation: There is no number at the left of 1. The smaller number than 6 and 2 is 1.

APPROACH:
To find the nearest smaller number on the left for each element, we can utilize a stack. 
We iterate through the array from left to right. For each element, we compare it with the elements in the stack. 
If an element in the stack is greater than or equal to the current element, we pop it from the stack since it cannot be the nearest smaller number on the left. 
The top of the stack at each iteration will hold the nearest smaller number on the left for the corresponding element in the array.

CODE:*/

vector<int> leftSmaller(int n, int arr[]) {
    stack<int> st;
    vector<int> ans(n, -1);

    for (int i = 0; i < n; i++) {
        while (!st.empty() && st.top() >= arr[i])
            st.pop();

        if (!st.empty())
            ans[i] = st.top();

        st.push(arr[i]);
    }

    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(N), where N is the length of the input array `a`. We iterate through the array once.
- The space complexity is O(N) as we use a stack to store the elements.
*/

/*QUESTION:
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

APPROACH:
To calculate the trapped water, we can use the two-pointer approach. We initialize two pointers, one at the beginning of the array (`left`) and another at the end of the array (`right`). We also maintain two variables, `leftMax` and `rightMax`, to keep track of the maximum bar height encountered from the left and right side, respectively.

1. Initialize `left` to 0 and `right` to the last index of the array.
2. Initialize `leftMax` and `rightMax` to the minimum integer value (`INT_MIN`).
3. Initialize `ans` (trapped water) to 0.
4. Iterate while `left` is less than or equal to `right`:
    a. If `height[left]` is less than `height[right]`:
        - Update `leftMax` if `height[left]` is greater than the current `leftMax`.
        - Calculate the amount of water trapped at the current `left` index by subtracting `height[left]` from `leftMax` and add it to `ans`.
        - Increment `left` by 1.
    b. Else:
        - Update `rightMax` if `height[right]` is greater than the current `rightMax`.
        - Calculate the amount of water trapped at the current `right` index by subtracting `height[right]` from `rightMax` and add it to `ans`.
        - Decrement `right` by 1.
5. Return the final value of `ans`.

CODE:*/
int trap(vector<int>& height) {
    int leftMax = INT_MIN;
    int rightMax = INT_MIN;
    int left = 0, right = height.size()-1;
    int ans = 0;

    while(left <= right) {
        if(height[left] < height[right]) {
            if(height[left] > leftMax)
                leftMax = height[left];
            else
                ans += leftMax - height[left];
            left++;
        } else {
            if(height[right] > rightMax)
                rightMax = height[right];
            else
                ans += rightMax - height[right];
            right--;
        }
    }

    return ans;
}
/*
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(N), where N is the number of elements in the `height` array. We iterate through the array once.
- The space complexity is O(1) as we only use a constant amount of extra space to store variables.
*/

/*QUESTION:
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

APPROACH:
To find the sum of the minimums of all subarrays, we can use the concept of previous smaller and next smaller elements for each element in the array.
1. Define two helper functions:
   - `prevSmaller(arr)`: Returns an array that contains the index of the previous smaller element for each element in `arr`. If no smaller element exists, the index is set to -1.
   - `nextSmaller(arr)`: Returns an array that contains the index of the next smaller element for each element in `arr`. If no smaller element exists, the index is set to the length of the array.
2. Initialize a variable `ans` to 0 to store the final sum.
3. Iterate over each element `arr[i]` in the array:
   a. Calculate the number of subarrays in which `arr[i]` is the minimum element.
      - The number of subarrays with `arr[i]` as the minimum element on the left side is `i - prevS[i]`.
      - The number of subarrays with `arr[i]` as the minimum element on the right side is `nextS[i] - i`.
   b. Add `(leftElements * rightElements * arr[i]) % mod` to `ans`, where `mod` is `1e9 + 7`.
4. Return the final value of `ans` as the sum of minimums of all subarrays modulo `1e9 + 7`.

CODE:*/
vector<int> prevSmaller(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), -1);
    for(int i = 0; i < arr.size(); i++){
        while(!st.empty() && arr[st.top()] > arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

vector<int> nextSmaller(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), arr.size());
    for(int i = arr.size()-1; i >= 0; i--){
        while(!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

int sumSubarrayMins(vector<int>& arr) {
    vector<int> prevS = prevSmaller(arr);
    vector<int> nextS = nextSmaller(arr);
    long long ans = 0;
    int mod = 1e9 + 7;

    for(int i = 0; i < arr.size(); i++){
        long long leftElements = i - prevS[i];
        long long rightElements = nextS[i] - i;
        // this formula is arrived by mathematical calculation
        ans += ((leftElements % mod) * (rightElements % mod) * (arr[i] % mod)) % mod;
    }

    return (int)ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(N), where N is the number of elements in the array `arr`. We iterate through the array twice to calculate the previous smaller and next smaller elements.
- The space complexity is O(N) as we use additional space to store the previous smaller and next smaller elements.
*/

/*QUESTION:
You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray. Return the sum of all subarray ranges of nums.

APPROACH:
To find the sum of all subarray ranges, we can use the concept of previous smaller, next smaller, previous greater, and next greater elements for each element in the array.
1. Define four helper functions:
   - `prevSmaller(arr)`: Returns an array that contains the index of the previous smaller element for each element in `arr`. If no smaller element exists, the index is set to -1.
   - `nextSmaller(arr)`: Returns an array that contains the index of the next smaller element for each element in `arr`. If no smaller element exists, the index is set to the length of the array.
   - `prevGreater(arr)`: Returns an array that contains the index of the previous greater element for each element in `arr`. If no greater element exists, the index is set to -1.
   - `nextGreater(arr)`: Returns an array that contains the index of the next greater element for each element in `arr`. If no greater element exists, the index is set to the length of the array.
2. Initialize a variable `ans` to 0 to store the final sum.
3. Iterate over each element `arr[i]` in the array:
   a. Calculate the number of subarrays where `arr[i]` is the minimum element:
      - The number of subarrays with `arr[i]` as the minimum element on the left side is `i - prevS[i]`.
      - The number of subarrays with `arr[i]` as the minimum element on the right side is `nextS[i] - i`.
   b. Calculate the number of subarrays where `arr[i]` is the maximum element:
      - The number of subarrays with `arr[i]` as the maximum element on the left side is `i - prevG[i]`.
      - The number of subarrays with `arr[i]` as the maximum element on the right side is `nextG[i] - i`.
   c. Update `ans` by adding `(maxleftElements * maxrightElements * arr[i]) - (minleftElements * minrightElements * arr[i])`.
4. Return the final value of `ans` as the sum of all subarray ranges.

CODE:*/

// NOTE:- The code could be more concise if done in double traversal but I find this more intuitive
vector<int> prevSmaller(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), -1);
    for(int i = 0; i < arr.size(); i++){
        while(!st.empty() && arr[st.top()] > arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

vector<int> nextSmaller(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), arr.size());
    for(int i = arr.size()-1; i >= 0; i--){
        while(!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

vector<int> prevGreater(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), -1);
    for(int i = 0; i < arr.size(); i++){
        while(!st.empty() && arr[st.top()] < arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

vector<int> nextGreater(vector<int>& arr){
    stack<int> st;
    vector<int> ans(arr.size(), arr.size());
    for(int i = arr.size()-1; i >= 0; i--){
        while(!st.empty() && arr[st.top()] <= arr[i])
            st.pop();
        if(!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

long long subArrayRanges(vector<int>& arr) {
    vector<int> prevS = prevSmaller(arr);
    vector<int> nextS = nextSmaller(arr);
    vector<int> prevG = prevGreater(arr);
    vector<int> nextG = nextGreater(arr);
    long long ans = 0;

    for(int i = 0; i < arr.size(); i++){
        long long minleftElements = i - prevS[i];
        long long minrightElements = nextS[i] - i;
        long long maxleftElements = i - prevG[i];
        long long maxrightElements = nextG[i] - i;
        ans += (maxleftElements * maxrightElements * arr[i]) - (minleftElements * minrightElements * arr[i]);
    }
    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of this approach is O(N), where N is the number of elements in the array `arr`. We iterate through the array multiple times to calculate the previous smaller, next smaller, previous greater, and next greater elements.
- The space complexity is O(N) as we use additional space to store the previous smaller, next smaller, previous greater, and next greater elements.
*/

/*
QUESTION:
Given string num representing a non-negative integer num, and an integer k,
return the smallest possible integer after removing k digits from num.

Example:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
*/

/*
APPROACH:
The idea is to use a stack to build the smallest number by removing larger digits.
We iterate through each digit in num and compare it with the digits in the stack.
If the current digit is smaller than the top of the stack, we pop elements from the stack
until either the stack is empty or the top of the stack is smaller than or equal to the current digit.
After processing all the digits, we remove any remaining digits from the stack to satisfy the required k digits to remove.
Finally, we construct the result by popping elements from the stack and reverse it to get the correct order.
*/

string removeKdigits(string num, int k) {
    stack<char> st;

    for (char c : num) {
        while (!st.empty() && k > 0 && st.top() > c) {
            st.pop();
            k--;
        }
        st.push(c);
    }

    // Remove remaining digits from the back if k is still greater than 0
    while (!st.empty() && k > 0) {
        st.pop();
        k--;
    }

    // Construct the result by popping elements from the stack
    string ans;
    while (!st.empty()) {
        ans.push_back(st.top());
        st.pop();
    }

    // Remove leading zeros
    reverse(ans.begin(), ans.end());
    while (!ans.empty() && ans.back() == '0') {
        ans.pop_back();
    }

    return ans.empty() ? "0" : ans;
}

/*
Complexity Analysis:
- The code iterates through each digit in the input string, so the time complexity is O(n),
  where n is the length of the input string.
- The space complexity is O(n) as well since the stack can potentially store all the digits in the input string.
*/

/*
QUESTION:
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1,
return the area of the largest rectangle in the histogram.

Example:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where the width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
*/

/*
APPROACH:
To find the largest rectangle area, we can use the concept of a stack.
The idea is to maintain a stack of indices of the heights in non-decreasing order.
For each height, we compare it with the top of the stack.
If the current height is greater than the top of the stack, we push its index onto the stack.
Otherwise, we keep popping elements from the stack and calculate the area using the popped index as the right boundary.
The left boundary can be obtained from the new top of the stack.
By doing this, we ensure that the heights in the stack are always in non-decreasing order.
Finally, we calculate the area for each popped element and update the maximum area found so far.

CODE:
*/


vector<int> prevSmaller(vector<int>& arr) {
    stack<int> st;
    vector<int> ans(arr.size(), -1);
    for (int i = 0; i < arr.size(); i++) {
        while (!st.empty() && arr[st.top()] > arr[i])
            st.pop();
        if (!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

vector<int> nextSmaller(vector<int>& arr) {
    stack<int> st;
    vector<int> ans(arr.size(), arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        while (!st.empty() && arr[st.top()] >= arr[i])
            st.pop();
        if (!st.empty())
            ans[i] = st.top();
        st.push(i);
    }
    return ans;
}

int largestRectangleArea(vector<int>& heights) {
    vector<int> prev = prevSmaller(heights);
    vector<int> next = nextSmaller(heights);

    int ans = INT_MIN;
    for (int i = 0; i < heights.size(); i++) {
        ans = max(ans, (next[i] - prev[i] - 1) * heights[i]);
    }
    return ans;
}

/*
COMPLEXITY ANALYSIS:
- The time complexity of the solution is O(n), where n is the number of elements in the heights array.
  This is because we iterate through the array once to calculate the previous and next smaller elements.
- The space complexity is O(n) as well since we use two additional arrays to store the previous and next smaller elements.
*/