GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
    Node* solution(vector<int>& nums,int left,int right){
        if(left>right) return NULL;
        if(left==right){
            return new Node(nums[left]);
        }
        int mid=(left+right)/2;
        Node* root=new Node(nums[mid]);
        root->left=solution(nums,left,mid-1);
        root->right=solution(nums,mid+1,right);
        return root;
    }
    Node* sortedArrayToBST(vector<int>& nums) {
        
        return solution(nums,0,nums.size()-1);
    }
};

class Solution {

  public:

     void tree(Node* &root ,vector<int> &bst){
        if(root==NULL)return;
        tree(root-> left , bst);
        bst.push_back(root -> data);
        tree(root-> right , bst);
        return ;
         }
    bool isBST(Node* root) {

         vector<int> bst;
        tree(root , bst);
        for(int i =0 ; i< bst.size() -1; i++){
            if(bst[i]>= bst[i+1]) return false;
        }
        return true;
    }
};

class Solution {
    void traverse(Node *root, vector<int> &ans){
        if(!root) return;
        traverse(root->left, ans);
        ans.push_back(root->data);
        traverse(root->right, ans);
    }
  public:

    vector<int> merge(Node *root1, Node *root2) {

        vector<int> ans;
        traverse(root1, ans);
        traverse(root2, ans);
        sort(ans.begin(), ans.end());
        return ans;
    }
};

Placement Finder 👨‍🎓

class Solution{
    public:
    bool solve(Node * root,int min,int max){
        if(root==NULL) return true;
        if(root->data<min || root->data>max){
            return false;
        }
        
        return solve(root->left,min,root->data-1) && 
        solve(root->right,root->data+1,max);
    }
    bool isbst(Node * root){
        bool ans=solve(root,INT_MIN,INT_MAX);
        return ans;
    }
    
    int size(Node * root){
        if(root==NULL) return 0;
        queue<Node *> q;
        q.push(root);
        int count=1;
        while(!q.empty()){
            Node * t=q.front();
            q.pop();
            if(t->left){
                q.push(t->left);
                count++;
            }
            if(t->right){
                q.push(t->right);
                count++;
            }
        }
        return count;
    }
    int largestBst(Node *root)
    {
        int ans=0;
        queue<Node *> q;
        q.push(root);
        while(!q.empty()){
            Node * temp=q.front();
            q.pop();
            if(isbst(temp)){
                ans=max(ans,size(temp));
            }
            
            if(temp->left){
                q.push(temp->left);
            }
            if(temp->right){
                q.push(temp->right);
            }
        }
        return ans;
    }
};

class Solution {
  public:
    long long int findMaxProduct(vector<int>& arr) {
        // Write your code here
        long long int mod = 1000000007;
        int zero = 0;//zero flag
        int pos = 0; //positive flag
        int neg = 0; //negative number count
        int maxNeg = INT_MIN; //maximum negative count
        long long int posPro = 1; //keep track of product of negative numbers
        long long int negPro = 1; //keep track of product of positive numbers
        
        for(int i = 0; i < arr.size(); i++){
            if(arr[i] == 0){
                zero = 1;
            }
            else if(arr[i] < 0){
                neg++;
                negPro = (negPro*arr[i])%mod;
                maxNeg = max(maxNeg, arr[i]);
            }
            else{
                pos = 1;
                posPro =(posPro*arr[i])%mod;
            }
        }
        
        if(pos == 0 && neg <= 1 && zero == 1) return 0;
        if(pos==1){
            if(neg%2 == 0){ //if negative numbers are in even then the product will be posiitve
                posPro = (posPro*negPro)%mod;
            }
            else if(neg%2!=0){//product will be negative
                posPro = (posPro*negPro/maxNeg)%mod ; // dividimg the maximum negative number to make the product positive
            }
            return posPro%mod;
        }
        if(pos==0 && neg > 1){
             if(neg%2!=0){
                negPro = (negPro/maxNeg)%mod ;
            }
            return negPro%mod;
        }
        return -1;
        
    }
};

Placement Finder 👨‍🎓

class Solution {
  public:
    Node *RemoveHalfNodes(Node *root) {
        if(!root)return root;
        Node*l = RemoveHalfNodes(root->left);
        Node*r = RemoveHalfNodes(root->right);
        if(root->left and root->right){
            root->left = l;
            root->right = r;
            return root;
        }
        else if(!root->left and !root->right){
            root->left = l;
            root->right = r;
            return root;
            
        }
        else if(root->left){
            root->left = l;
            return root->left;
        }
        else if(root->right){
            root->right = r;
            return root->right;
        }
        else{
            return nullptr;
        }
    }
};

class Solution {
  public:
    vector<int> seg;
    
    void update(int i, int j, int l, int h){
        if(j < l || j > h)
            return;
        seg[i]++;
        // cout << l <<" "<<h<<" "<<seg[i]<<endl;
        if(l == h)
            return;
        int mid = (l+h)>>1;
        update(2*i + 1, j, l, mid);
        update(2*i + 2, j, mid+1, h);
    }
    int query(int i, int j, int l, int h){
        if(h < j)
            return 0;
        if(l >= j)
            return seg[i];
        int mid = (l+h)>>1;
        return query(2*i+1, j, l, mid) +
        query(2*i+2, j, mid+1, h);
    }
    vector<int> constructLowerArray(vector<int> &arr) {
    
        int n = arr.size();
        seg.resize(4*n);
        vector<int> ans(n);
        vector<vector<int>> temp;
        for(int i=0;i<n;i++){
            temp.push_back({arr[i], i});
        }
        sort(temp.begin(), temp.end());
        
        for(int i=0;i<n;i++){
            ans[temp[i][1]] = query(0, temp[i][1], 0, n-1);
            update(0,temp[i][1],0,n-1);
        }
        return ans;
    }
};