Tag: GFG PTOD

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;
    }

int height(Node* node, int &dia) {
        // code here
        if(node == NULL) return 0;
        int lh = height(node->left,dia);
        int rh = height(node->right,dia);
        dia = max(dia, lh+rh);
        return max(lh, rh) +1;
    }
    int diameter(Node* root) {
        // Your code here
        int diameter = 0;
        height(root, diameter);
        return diameter;
    }

vector<vector<int>> levelOrder(Node *root) {
        // Your code here
        vector<vector<int>> ans;
        if(root == NULL) return ans;
        queue<Node*> q;
        q.push(root);
        while(!q.empty()) {
            vector<int> res;
            int len = q.size();
            for(int i=0; i<len; i++) {
                Node *cur = q.front();
                q.pop();
                res.push_back(cur->data);
                if(cur->left) q.push(cur->left);
                if(cur->right) q.push(cur->right);
            }
            ans.push_back(res);
        }
        return ans;
    }

bool solve(vector<vector<char>>& mat, string& word, int i, int j, int widx) {
        int wlen = word.length();
        int n = mat.size();
        int m = mat[0].size();
        //base case
        if(widx == wlen) return true;
        if(i<0 || j<0 || i>=n || j>=m) return false;
        //recursive case
        if(mat[i][j] == word[widx]) {
            bool res = false;
            char tmp = mat[i][j];
            mat[i][j] = '_';
            if(solve(mat, word, i-1, j, widx+1) || solve(mat, word, i+1, j, widx+1) ||
                solve(mat, word, i, j+1, widx+1) || solve(mat, word, i, j-1, widx+1)) 
                    res = true;
            mat[i][j] = tmp;
            return res;
        }
        return false;
    }
    bool isWordExist(vector<vector<char>>& mat, string& word) {
        // Code here
        int n = mat.size();
        int m = mat[0].size();
        int wlen = word.length();
        for(int i=0;i<n; i++) {
            for(int j=0; j<m; j++) {
                if(solve(mat, word, i, j, 0)) return true;
            }
        }
        return false;
    }

bool setisfy(vector<vector<int>> &mat, int i, int j, int num) {
        for(int x= 0; x<9; x++) {
            if(mat[i][x] == num || mat[x][j] == num) 
                return false;
        }
        int str = i-i%3, stc = j-j%3;
        for(int a=0; a<3; a++){
            for(int b=0;b<3; b++) {
                if(mat[str+a][stc+b] == num)
                    return false;
            }
        }
        return true;
    }
    
    bool solve(vector<vector<int>> &mat)  {
        for(int i=0; i<9; i++) {
            for(int j=0; j<9; j++) {
                if(mat[i][j] == 0) {
                    for(int num = 1; num<=9; num++) {
                        if(setisfy(mat, i, j, num)) {
                            mat[i][j] = num;
                            if(solve(mat)) return true;
                            mat[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    // Function to find a solved Sudoku.
    void solveSudoku(vector<vector<int>> &mat) {
        // code here
        solve(mat);
    }