Category: DS & Algo

string decodedString(string &s) {
        // code here
        stack<char> st;
        string ans;
        for(int i=0;i<s.size(); i++) {
            if(s[i] != ']') st.push(s[i]);
            else {
                string temp;
                while(!st.empty() && st.top() != '[') {
                    temp.push_back(st.top());
                    st.pop();
                }
                reverse(temp.begin(), temp.end());
                st.pop();
                string dig;
                while(!st.empty() && isdigit(st.top())) {
                    dig.push_back(st.top());
                    st.pop();
                }
                reverse(dig.begin(), dig.end());
                string word;
                for(int j=0; j<stoi(dig); j++) {
                    word.append(temp);
                }
                for(char c:word) 
                    st.push(c);
            }
        }
        while(!st.empty()) {
            ans.push_back(st.top());
            st.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans; 
    }

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

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

int maxLength(string& s) {
        // code here
        int maxlen = 0;
        stack<int> st;
        st.push(-1);
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '(') st.push(i);
            else {
                st.pop();
                if(!st.empty()) maxlen = max(maxlen, i-st.top());
                else st.push(i);
            }
        }
        return maxlen;
    }

 bool isBalanced(string& s) {
        // code here
        // with stack
        stack<char> ch;
        for(int i=0; i<s.size(); i++) {
            if(s[i] == '[' || s[i] == '{' || s[i] == '(')
                ch.push(s[i]);
            else {
                if(!ch.empty() && ((s[i] == ']' && ch.top() == '[') ||
                                    (s[i] == '}' && ch.top() == '{') || 
                                    (s[i] == ')' && ch.top() == '(')))
                    ch.pop();
                else
                    return false;
            }
        }
        if(ch.empty()) return true;
        return false;
    }

vector<double> getMedian(vector<int> &arr) {
        // code here
        vector<double> ans;
        priority_queue<int> maxheap;
        priority_queue<int, vector<int>, greater<int>> minheap;
        for(int i=0; i<arr.size(); i++) {
            if(maxheap.empty() || arr[i] <= maxheap.top()) maxheap.push(arr[i]);
            else minheap.push(arr[i]);
            //cout << "min " << minheap.size() << ", max " << maxheap.size() << endl;
            if(maxheap.size() > minheap.size()+1) {
                minheap.push(maxheap.top());
                maxheap.pop();
            } else if(minheap.size() > maxheap.size()) {
                maxheap.push(minheap.top());
                minheap.pop();
            }
            //cout << "minS " << minheap.size() << ", maxS " << maxheap.size() << endl;
            double mid = 0;
            if(maxheap.size() > minheap.size()) mid = maxheap.top();
            else {
                //cout << "minh " << minheap.top() << ", maxh " << maxheap.top() << endl;
                mid = (double)(minheap.top()+maxheap.top())/2;
            }
            //cout << "mid : " << mid << endl;
            ans.push_back(mid);
        }
        return ans;
    }

void pre(Node *root, vector<int> &ans) {
        if(!root) {
            ans.push_back(-1);
            return;
        }
        ans.push_back(root->data);
        pre(root->left, ans);
        pre(root->right, ans);
    }
    // Function to serialize a tree and return a list containing nodes of tree.
    vector<int> serialize(Node *root) {
        // Your code here
        vector<int> ans;
        pre(root, ans);
        return ans;
    }

    int i = 0;
    // Function to deserialize a list and construct the tree.
    Node *deSerialize(vector<int> &arr) {
        // Your code here
        int val = arr[i];
        i++;
        if(val == -1) return NULL;
        Node *tmp = new Node(val);
        tmp->left = deSerialize(arr);
        tmp->right = deSerialize(arr);
        return tmp;
    }

bool isLeaf(Node *root) {
        if(root->left == NULL && root->right == NULL)
            return true;
        return false;
    }
    void leftBoundry(Node *root, vector<int> &res) {
        if(root == NULL || isLeaf(root)) return;
        res.push_back(root->data);
        if(root->left) leftBoundry(root->left, res);
        else if(root->right) leftBoundry(root->right, res);
    }
    void leafBoundry(Node *root, vector<int> &res) {
        if(root == NULL) return;
        if(isLeaf(root)) {
            res.push_back(root->data);
            return;
        }
        leafBoundry(root->left, res);
        leafBoundry(root->right, res);
    }
    void rightBoundry(Node *root, vector<int> &res) {
        if(root == NULL || isLeaf(root)) return;
        if(root->right) rightBoundry(root->right, res); 
        else if(root->left) rightBoundry(root->left, res);
        res.push_back(root->data);
    }
    vector<int> boundaryTraversal(Node *root) {
        // code here
        vector<int> res;
        if(!root) return res;
        if(!isLeaf(root)) res.push_back(root->data);
        leftBoundry(root->left, res);
        leafBoundry(root, res);
        rightBoundry(root->right, res);
        
        return res;
    }

void trverse(Node* root, vector<int> &res) {
        if(!root) return;
        trverse(root->left, res);
        res.push_back(root->data);
        trverse(root->right, res);
    }
    // Function to return a list containing the inorder traversal of the tree.
    vector<int> inOrder(Node* root) {
        // Your code here
        vector<int> res;
        trverse(root, res);
        return res;
    }