GeeksForGeeks - POTD | GFG POTD Answer

class DisjointSet{
  public:
  DisjointSet() = delete;
  DisjointSet(int n){
      rank.resize(n+1, 0); //N+1 because graph might be 1 based indexing
      parent.resize(n+1);
      size.resize(n+1, 1);
      std::iota(begin(parent), end(parent), 0);
  }
  
  int getUlParent(int node){ //get ultimate parent
      if(node == parent[node]){
          return node;
      }else{
          return parent[node] = getUlParent(parent[node]);
      }
  }
  
  void unionByRank(int u, int v){
      int ulp_u = getUlParent(u);
      int ulp_v = getUlParent(v);
      if(ulp_u == ulp_v){
          return;
      }
      if(rank[ulp_u] < rank[ulp_v]){
          parent[ulp_u] = ulp_v;
      }else if(rank[ulp_v] < rank[ulp_u]){
          parent[ulp_v] = ulp_u;
      }else{
          parent[ulp_u] = ulp_v;
          rank[ulp_u]++;
      }
  }
  void unionBySize(int u, int v){
      int ulp_u = getUlParent(u);
      int ulp_v = getUlParent(v);
      if(ulp_u == ulp_v){
          return;
      }
      if(rank[ulp_u] < rank[ulp_v]){
          parent[ulp_u] = ulp_v;
          size[ulp_u] += size[ulp_v];
      }else{
          parent[ulp_v] = ulp_u;
          size[ulp_v] += size[ulp_u];
      }
  }
  private:
  vector<int> rank, parent, size;
};
class Solution{
  public:
    vector<vector<string>> accountsMerge(vector<vector<string>> &accounts) {
        
        int n = accounts.size(), i, j;
        DisjointSet dsj(n+1);
        unordered_map<string, int> mp;
        vector<vector<string>> res;
        for(i = 0;i<n;i++){
            for(j = 1;j<accounts[i].size();j++){
                if(!mp[accounts[i][j]]){
                    mp[std::move(accounts[i][j])] = i+1;
                }else{
                    dsj.unionByRank(mp[accounts[i][j]], i+1);
                }
            }
        }
        vector<string> adj[n+1];
        for(auto itr{begin(mp)}; itr != end(mp); ++itr){
            adj[dsj.getUlParent(itr->second)].push_back(std::move(string(itr->first)));
        }
        for(i = 1;i<=n;i++){
            if(adj[i].size()){
                sort(adj[i].begin(), adj[i].end());
                adj[i].insert(adj[i].begin(), std::move(accounts[i-1][0]));
                res.push_back(std::move(adj[i]));
            }
        }
        
        return res;
    }
};

class Solution {
  private:
  bool check(vector<vector<int>>&a, int mid){
      int m = a.size();
      int n = a[0].size();
      vector<int> xdir {0, 0, 1, -1};
      vector<int> ydir {1, -1, 0, 0};
      bool visited[m][n];
      memset(visited, false, sizeof(visited));
      visited[0][0] = true;
      queue<pair<int, int>> q;
      q.push({0, 0});
      while(q.empty() == false){
          auto curr = q.front();
          q.pop();
          int x = curr.first;
          int y = curr.second;
          if (x == m - 1 && y == n - 1){
              return true;
          }
          for(int k = 0; k < 4; k++){
              int newX = x + xdir[k];
              int newY = y + ydir[k];
              if(newX >= 0 && newY >= 0 && newX < m && newY < n && visited[newX][newY] == false && abs(a[x][y] - a[newX][newY]) <= mid){
                  visited[newX][newY] = true;
                  q.push({newX, newY});
              }
          }
      }
      return false;
  }
    
  public:
    int MinimumEffort(int rows, int columns, vector<vector<int>> &heights) {
        int low = 0;
        int high = 1e6;
        while(low < high){
            int mid = low + (high - low)/2;
            if(check(heights, mid)){
                high = mid;
            }
            else{
                low = mid + 1;
            }
        }
        return low;
    }
};

class Solution {
  private:
    void dfs(vector<vector<int>> &adj, int i, vector<int> &isVisited, vector<int> &temp){
        temp.push_back(i);
        isVisited[i]++;
        for(auto &it : adj[i]){
            if(isVisited[it] == 0)
                dfs(adj, it, isVisited, temp);
        }
        return;
    }
  public:
    int findNumberOfGoodComponent(int e, int v, vector<vector<int>> &edges) {
        vector<vector<int>> adj(v + 1, vector<int> {});
        for(auto &e: edges){
            int a = e[0];
            int b = e[1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        int numberOfGoodComponents = 0;
        vector<int> isVisited (v + 1, 0);
        for(int i = 1; i <= v; i++){
            if(isVisited[i] == 0){
                vector<int> temp;
                dfs(adj, i, isVisited, temp);
                bool flag = true;
                for(auto &it : temp){
                    if(adj[it].size() != temp.size() - 1){
                        flag = false;
                        break;
                    }
                }
                if (flag){
                    numberOfGoodComponents++;
                }
            }
        }
        return numberOfGoodComponents;
    }
};

class Solution {
  public:
    int minSteps(int d) {
        int pos=0,step=0;
        while(pos<d||((pos-d)%2!=0)){
            step++;
            pos+=step;
            
        }
        return step;
    }
};

class Solution {
  public:
    vector<int> jugglerSequence(int n) {
         vector<int> ans;
        while(n!=1){
            ans.push_back(n);
            if(n%2==0){
                n=pow(n,0.5);
            }else{
                n=pow(pow(n,3),0.5);
            }
        }
           ans.push_back(n);
        return ans;
    }
};

class Solution{
    private:
    void solve(int ind,int n,int target,vector<int>&nums,vector<int>&temp,vector<vector<int>>&ans)
    {
        if(target==0)
        {
            ans.push_back(temp);
            return ;
        }
        for(int i=ind;i<n;++i)
        {
            if(i>ind and nums[i]==nums[i-1]) continue;
            if(nums[i]>target) break;
            
            temp.push_back(nums[i]);
            solve(i+1,n,target-nums[i],nums,temp,ans);
            temp.pop_back();
        }
    }
public:
    vector<vector<int>> CombinationSum2(vector<int> arr,int n,int k)
    {
        sort(arr.begin(),arr.end());
        vector<vector<int>>ans;
        vector<int>temp;
        solve(0,n,k,arr,temp,ans);
        return ans;
    }
};

class Solution {
  public:
    bool divisorGame(int n) {
        return !(n & 1);
    }
};

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

};

vector<int> reverseLevelOrder(Node *root)
{
    vector<int> res;
    queue<Node *> q;
    
    q.push(root);
    while(!q.empty()) 
    {
        auto p = q.front();
        q.pop();
        
        res.push_back(p->data);
        
        if(p->right)
            q.push(p->right);
            
        if(p->left)
            q.push(p->left);
    }
    
    reverse(res.begin(), res.end());
    return res;
}