GeeksForGeeks - POTD | GFG POTD Answer

class Solution {
  public:
    vector<int> dirX={1,0,0,-1};
    vector<int> dirY={0,1,-1,0};
    void dfs(vector<vector<int>> &parent,map<int,int>&mp,int p,int i,int j, vector<vector<int>>&grid){
        if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || parent[i][j]!=-1 || grid[i][j]!=1){
            return;
        }
        parent[i][j]=p;
        mp[p]++;
        for(int k=0;k<4;k++){
            dfs(parent,mp,p,i+dirX[k],j+dirY[k],grid);
        }
    }
    int MaxConnection(vector<vector<int>>& grid) {
        vector<vector<int>> parent(grid.size(),vector<int>(grid[0].size(),-1));
        map<int,int> mp;
        int p=1;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==1 && parent[i][j]==-1){
                    dfs(parent,mp,p,i,j,grid);
                    p++;
                }
            }
        }
        
        int maxi=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[i].size();j++){
                if(grid[i][j]==0){
                    set<int> s;
                    int curr=1;
                    for(int k=0;k<4;k++){
                        int x=i+dirX[k];
                        int y=j+dirY[k];
                        if(x>-1 && y>-1 && x<grid.size() && y<grid[0].size()){
                            if(parent[x][y]!=-1 && s.find(parent[x][y])==s.end()){
                                s.insert(parent[x][y]);
                                curr+=mp[parent[x][y]];
                            }
                        }
                    }
                   
                    maxi=max(curr,maxi);
                }
            }
        }
        for(auto &i:mp){
            maxi=max(maxi,i.second);
        }
        
        return maxi;
    }
};

class Solution {
  public:
    int maxSquare(int n, int m, vector<vector<int>> mat) {
        vector<vector<int>> dp(n,vector<int> (m,0));
        int maxi =0;
        for(int i =0;i< max(n,m);i++){
            if(i < m && mat[n -1][i] == 1){
                dp[n -1][i] =1;
                maxi =max(maxi,dp[n -1][i]);
            }
            if(i < n && mat[i][m -1] == 1){
                dp[i][m -1] =1;
                maxi =max(maxi,dp[i][m -1]);
            }
        }
        for(int i=n -2;i>=0;i--){
            for(int j =m -2;j>=0;j--){
                if(mat[i][j]){
                    dp[i][j] =1 + min(dp[i +1][j +1],min(dp[i +1][j],dp[i][j +1]));
                }else{
                    dp[i][j] =0;
                }
                maxi =max(dp[i][j],maxi);
            }
        }
        return maxi;
    }
};

class Solution {
  public:
    int threeSumClosest(vector<int> arr, int target) {
        
        int dif=INT_MAX,ans=INT_MIN;
        sort(arr.begin(),arr.end());
        for(int i=0;i<arr.size();i++){
            int start=i+1;
            int end=arr.size()-1;
            while(start<end){
                int sum=arr[i]+arr[start]+arr[end];
                if(sum==target)return sum;
                else if(sum>target) end--;
                else start++;
                if(abs(sum-target)<dif){
                    dif=abs(sum-target);
                    ans=sum;
                }
                else if(abs(sum-target)==dif){
                    ans=max(ans,sum);
                }
            }
        }
        return ans;
    }
};

⚠ Important Announcement

class Solution {
  public:
    int search(vector<int>& arr, int key) {
        int s = 0, e = arr.size() - 1;
        while(s <= e)
        {
            if(arr[s] == key)
            {
                return s;
            }
            else{
                s++;
            }
            if(arr[e] == key)
            {
                return e;
            }
            else{
                e--;
            }
        }
        return -1;
    }
};

class Solution {
  public:
  bool ancestor(vector<int>&ans,struct Node *root,int target){
      if(root==NULL){
          return false;
      }
      if(ancestor(ans,root->left,target)){
          ans.push_back(root->data);
          return true;
      }
      if(root->data==target){
          return true;
      }
      if(ancestor(ans,root->right,target)){
          ans.push_back(root->data);
          return true;
      }
      return false;
  }
    // Function should return all the ancestor of the target node
    vector<int> Ancestors(struct Node *root, int target) {
        
        vector<int>ans;
        ancestor(ans,root,target);
        return ans;
    }
};

• Abdul Bari Udemy Course Link • Abdul Bari Mega Link • Abdul Bari DSA Course

Decryption Key 🔑 - Tap To Copy

class Solution {
  public:
    void inorder(Node* root, vector<Node*> &in)
    {
        if(!root)
        {
            return;
        }
        
        inorder(root->left, in);
        in.push_back(root);
        inorder(root->right, in);
    }
    
    void populateNext(Node *root) {
        vector<Node*> in;
        
        inorder(root, in);
    
        for(int i = 0; i < in.size() - 1; i++)
        {
            in[i]->next = in[i+1];
        }
        
        root= in[0];
        
    }
};