LeetCode, GeeksForGeeks Problem of the day solution

class Solution { public: vector getRow(int rowIndex) { vector> pasc(rowIndex+1); for(int i=0;i<=rowIndex;i++){ pasc[i].resize(i+1); pasc[i][0] = pasc[i][i] = 1; for(int j=1;j

class DisjointSet { public: vector rank, parent, size; DisjointSet(int n) { rank.resize(n + 1, 0); parent.resize(n + 1); size.resize(n + 1); for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; } } int findUPar(int node) { if (node == parent[node]) return node; return parent[node] = findUPar(parent[node]); } void unionByRank(int u, int v) { int ulp_u = findUPar(u); int ulp_v = findUPar(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_v] = ulp_u; rank[ulp_u]++; } } void unionBySize(int u, int v) { int ulp_u = findUPar(u); int ulp_v = findUPar(v); if (ulp_u == ulp_v) return; if (size[ulp_u] < size[ulp_v]) { parent[ulp_u] = ulp_v; size[ulp_v] += size[ulp_u]; } else { parent[ulp_v] = ulp_u; size[ulp_u] += size[ulp_v]; } } }; class Solution { private: bool isValid(int newr, int newc, int n) { return newr >= 0 && newr < n && newc >= 0 && newc < n; } public: int largestIsland(vector>& grid) { int n = grid.size(); DisjointSet ds(n * n); // step - 1 for (int row = 0; row < n ; row++) { for (int col = 0; col < n ; col++) { if (grid[row][col] == 0) continue; int dr[] = { -1, 0, 1, 0}; int dc[] = {0, -1, 0, 1}; for (int ind = 0; ind < 4; ind++) { int newr = row + dr[ind]; int newc = col + dc[ind]; if (isValid(newr, newc, n) && grid[newr][newc] == 1) { int nodeNo = row * n + col; int adjNodeNo = newr * n + newc; ds.unionBySize(nodeNo, adjNodeNo); } } } } // step 2 int mx = 0; for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { if (grid[row][col] == 1) continue; int dr[] = { -1, 0, 1, 0}; int dc[] = {0, -1, 0, 1}; set components; for (int ind = 0; ind < 4; ind++) { int newr = row + dr[ind]; int newc = col + dc[ind]; if (isValid(newr, newc, n)) { if (grid[newr][newc] == 1) { components.insert(ds.findUPar(newr * n + newc)); } } } int sizeTotal = 0; for (auto it : components) { sizeTotal += ds.size[it]; } mx = max(mx, sizeTotal + 1); } } for (int cellNo = 0; cellNo < n * n; cellNo++) { mx = max(mx, ds.size[ds.findUPar(cellNo)]); } return mx; } };

class Solution { public: int numWays(int steps, int arrLen) { int s=arrLen; int k=min(s,steps); vector> dp(steps+1,vector (k,0)); dp[0][0]=1; int mod=1e9+7; for(int i=1;i=0){ left=dp[i-1][j-1]; } if(j+1

class Solution{ public: // Your are required to complete this function // function should return root of the modified BST void inOrderUtil(Node *root, vector<int>&nodes) { if(root == NULL) return; inOrderUtil(root->left,nodes); nodes.push_back(root->data); inOrderUtil(root->right,nodes); } Node *createBstFromInorder(vector<int>&nodes, int l, int r) { if( l > r) return NULL; int mid = (l + r)/2; Node *root = new Node(nodes[mid]); root->left = createBstFromInorder(nodes,l,mid-1); root->right = createBstFromInorder(nodes,mid+1,r); return root; } public: // Your are required to complete this function // function should return root of the modified BST Node* buildBalancedTree(Node* root) { if(root == NULL) return NULL; vector<int>nodes; inOrderUtil(root,nodes); int size = nodes.size(); return createBstFromInorder(nodes,0,size-1); } };

class Solution { public: int n; int dp[501][501]; int solve(vector&cost,vector&time,int i,int walls) { if(walls<=0) { return 0; } if(i>=n) { return 1e9; } if(dp[i][walls]!=-1) { return dp[i][walls]; } int paid=cost[i]+solve(cost,time,i+1,walls-1-time[i]); int npaid=solve(cost,time,i+1,walls); return dp[i][walls]=min(paid,npaid); } int paintWalls(vector& cost, vector& time) { memset(dp,-1,sizeof(dp)); n=cost.size(); return solve(cost,time,0,n); } };

class Solution { public: //Function to find the nodes that are common in both BST. void insert(Node *root,set&s) { if(root==NULL)return ; insert(root->left,s); s.insert(root->data); insert(root->right,s); } vector findCommon(Node *root1, Node *root2) { //Your code here sets1,s2; insert(root1,s1); insert(root2,s2); vectorans; for(auto i:s1) { if(s2.find(i)!=s2.end()) ans.push_back(i); } return ans; } };

class Solution { public: int minCostClimbingStairs(vector& cost) { int n= cost.size(); if(n==1){ return cost[0]; } vector dp(n+1, 0); dp[0] = cost[0]; dp[1] = cost[1]; for(int i=2;i

class Solution{ public: int floor(Node* root, int x) { if(root==NULL){ return -1; } int res=-1; while(root){ if(root->data==x){ res= root->data; return res; } else if(x > root->data){ res = root->data; root= root->right; } else{ root= root->left; } } return res; } };

class Solution { private: int bs(int s,int e,int tar,MountainArray &arr,bool flag) { while(s<=e){ int mid=s+(e-s)/2; int midVal=arr.get(mid); if(midVal==tar) return mid; if(flag==(midVal>tar)) s=mid+1; else e=mid-1; } return -1; } public: int findInMountainArray(int tar, MountainArray &arr) { int s=0,e=arr.length()-1,peak=0; while(s<e){ int mid=s+(e-s)/2; if(arr.get(mid)<arr.get(mid+1)) s=peak=mid+1; else e=mid; } int ans=bs(0, peak, tar,arr,false); int res=bs(peak+1,arr.length()-1,tar,arr,true); return (ans!=-1) ? ans : res; } };

class Solution { public: /*This function returns true if the tree contains a duplicate subtree of size 2 or more else returns false*/ unordered_map mp; string solve(Node* node) { if(node==NULL)return ""; string ans=""; string l=solve(node->left); string r=solve(node->right); ans=l+"#"+to_string(node->data)+"#"+r; if(node->left || node->right)mp[ans]++; return ans; } int dupSub(Node *root) { string x=solve(root); for(auto o:mp) { if(o.second>1) { return true; } } return false; // code here } };