LeetCode, GeeksForGeeks Problem of the day solution
Kanalga Telegram’da o‘tish
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
Ko'proq ko'rsatish1 250
Obunachilar
+224 soatlar
+147 kunlar
+2930 kunlar
Postlar arxiv
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
}
};
