Відео

Nice video, very conceptual

int fun(int i,int j,string s1,string s2,vector<vector<int>>&dp){ if(i == s1.size() && j == s2.size()) return 0; if(i > s1.size() || j > s2.size()) return 1e9; if(dp[i][j]!= -1) return dp[i][j]; int p = 1e9; if(s1[i] == s2[j]){ p = fun(i+1,j+1,s1,s2,dp); } int case1 = 1 + fun(i+1,j,s1,s2,dp); int case2 = 1 + fun(i,j+1,s1,s2,dp); int case3 = 1 + fun(i+1,j+1,s1,s2,dp); return dp[i][j] = min(p,min(case1,min(case2,case3))); } class Solution { public: int editDistance(string str1, string str2) { int n = str1.size(); int m = str2.size(); vector<vector<int>>dp(n+1,vector<int>(m+1,-1)); return fun(0,0,str1,str2,dp); } };

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

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

code bro?

Why map[root->data]++ is ++ is necessary 🤔

class Solution{ public: /*You are required to complete this method */ // Return the size of the largest sub-tree which is also a BST int nodes(Node * root){ if(root==NULL)return 0; return 1 + nodes(root->left)+ nodes(root->right); } bool bst(Node * root,int x,int y){ if(root==NULL)return true; if(x<root->data && y>root->data){ bool a = bst( root->left,x,root->data); bool b = bst(root->right,root->data,y); return a&b; } else return false; } int largestBst(Node *root) { if(bst(root,INT_MIN,INT_MAX)) return nodes(root); return max(largestBst(root->left),largestBst(root->right)); } };

class Solution { public: int bs(vector<int>&temp,int var){ int n = temp.size(); int low = 0; int high = n-1; int ans = -1; while(low<=high){ int mid = (low+high)/2; if(temp[mid]==var){ ans = mid; high = mid-1; } if(temp[mid]<var){ low = mid+1; } else{ high = mid - 1; } } return ans; } vector<int> constructLowerArray(vector<int> &arr) { // code here int n = arr.size(); vector<int>temp(arr.begin(),arr.end()); sort(temp.begin(),temp.end()); vector<int>ans(n,0); for(int i =0;i<n;i++){ int f = arr[i]; int id = bs(temp,f); ans[i] = id; temp.erase(temp.begin()+id); } return ans; } };

How do you get this idea bro? Really awesome bro.

class Solution { public: // Function to construct binary tree from parent array. Node *createTree(vector<int> parent) { int n = parent.size(); map<int,Node*>mpp; for(int i=0;i<n;i++){ mpp[i] = new Node(i); } Node * head ; for(int i=0;i<n;i++){ if(parent[i]==-1){ head = mpp[i]; } else{ if(!mpp[parent[i]]->left){ mpp[parent[i]]->left=mpp[i]; } else{ mpp[parent[i]]->right = mpp[i]; } } } return head; } };

class Solution { public: string smallestNumber(int s, int d) { // code here if(s>9*d)return "-1"; string ans = ""; int k = s; k-=1; for(int i=1;i<=d;i++){ if(k>9){ k-=9; ans+='9'; } else{ if(i==d){ k++; } string store = to_string(k); ans += store; k=0; } } reverse(ans.begin(),ans.end()); return ans; } };

class Solution { public: void segregate0and1(vector<int> &arr) { int l = 0;int r = arr.size()-1; while(l < r){ if(arr[l] == 0 && arr[r] == 0){ l++; } else if(arr[l] == 0 && arr[r] == 1){ l++;r--; } else if(arr[l] == 1 && arr[r] == 0){ swap(arr[l],arr[r]); l++;r--; } else{ r--; } } } };

code : /* A binary tree node struct Node { int data; Node* left, * right; }; */ /*you are required to complete this function */ class Solution { public: bool func(Node * root,int t,int x){ if(root==NULL)return false; else if(root->left==NULL && root->right==NULL ){ if(x+root->data==t)return true; return false; } bool left = func(root->left,t,x+root->data); bool right = func(root->right,t,x+root->data); return left||right; } bool hasPathSum(Node *root, int target) { // Your code here return func(root,target,0); } };

Zenitsu😂

can you explain me this at 14:30 already name give to the the index-> if(grid[i][j]==1){ int grp = dfs(ind,i,j,grid); mpp[ind] = grp; ind ++; ----> here every time we increment it ans = max(ans,grp); } so lets jus say at(0,0) -> 1 is present so we will name this as 2 and for (0,1) then it will be name as 3? coz in for loop we did this for each element(ind ++;)

// User function Template for C++ code class Solution { public: int dfs(int ind,int i,int j,vector<vector<int>>&grid){ if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]==0 || grid[i][j]==ind){ return 0; } grid[i][j] = ind; int a = dfs(ind,i+1,j,grid); int b = dfs(ind,i,j+1,grid); int c = dfs(ind,i-1,j,grid); int d = dfs(ind,i,j-1,grid); return 1 + a+ b+ c+ d; } int MaxConnection(vector<vector<int>>& grid) { // code here int n = grid.size(); int ans =0; map<int,int>mpp; int ind = 2; for(int i=0;i<n;i++){ for(int j =0;j<n;j++){ if(grid[i][j]==1){ int grp = dfs(ind,i,j,grid); mpp[ind] = grp; ind ++; ans = max(ans,grp); } } } // ans == max_area without converting from 0 to 1 for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==0){ int maxi = 0; set<int>st; if(i>0)st.insert(grid[i-1][j]); if(j>0)st.insert(grid[i][j-1]); if(i<n-1)st.insert(grid[i+1][j]); if(j<n-1)st.insert(grid[i][j+1]); for(auto it:st){ maxi += mpp[it]; } maxi++; ans = max(ans,maxi); } } } return ans; } };

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

// User function template for C++ // arr : given vector of elements // target : given sum value class Solution { public: int threeSumClosest(vector<int> arr, int target) { // Your code goes here int n = arr.size(); int diff = INT_MAX; int ans = INT_MAX; sort(arr.begin(),arr.end()); for(int i=0;i<n-2;i++){ int a = i+1; int b = n-1; while(a<b){ int _sum = arr[i]+ arr[a]+ arr[b]; int m = abs(_sum - target); if(m<diff){ diff = m; ans = _sum; } if(m== diff&& _sum>ans){ ans = _sum; } if(_sum>target)b--; else if(_sum<target)a++; else if(_sum==target)break; } } return ans; } };

// User function template for C++ /* Structure of a node is as following struct Node { int data; struct Node* left; struct Node* right; }; */ class Solution { public: // Function should return all the ancestor of the target node vector<int>ans; void trav(Node * root,vector<int>ds,int x){ if(root==NULL){return;} if(root->data == x){ ans = ds; return; } ds.push_back(root->data); trav(root->left,ds,x); trav(root->right,ds,x); } vector<int> Ancestors(struct Node *root, int target) { vector<int>ds; trav(root,ds,target); reverse(ans.begin(),ans.end()); return ans; } };

class Solution { public: Node* prev = NULL; void populateNext(Node *root) { if(root == NULL) return; populateNext(root->left); if(prev) prev->next = root; prev = root; populateNext(root->right); } };

class Solution { public: // Function to find the vertical width of a Binary Tree. void func(Node * root,int i,int &x,int &y){ if(root==NULL)return; x = min(x,i); y = max(y,i); func(root->left,i-1,x,y); func(root->right,i+1,x,y); } int verticalWidth(Node* root) { // code here if(root==NULL)return 0; int x = INT_MAX; int y = INT_MIN; func(root,0,x,y); return y-x+1; } };

string fun(Node* root,unordered_map<string,int>&mp,vector<Node*>&ans){ if(root== NULL) return "N"; string l = fun(root->left,mp,ans); string r = fun(root->right,mp,ans); string subTree = l + to_string(root->data) + r; if(mp[subTree] == 1){ ans.push_back(root); } mp[subTree]++; return subTree; } class Solution { public: vector<Node*> printAllDups(Node* root) { unordered_map<string ,int>mp; vector<Node*> ans; fun(root,mp,ans); return ans; } };

code : /* The structure of Link list Node is as follows struct Node { int data; struct node* next; Node(int x){ data = x; next = NULL; } }; The structure of TreeNode is as follows struct TreeNode { int data; TreeNode *left; TreeNode *right; }; */ // Function to make binary tree from linked list. vector<int>func(Node * head){ Node * head1 = head; vector<int>ans; while(head1!=NULL){ ans.push_back(head1->data); head1=head1->next; } return ans; } void convert(Node *head, TreeNode *&root) { if(head==NULL){ root=NULL; return; } vector<int>arr = func(head); root = new TreeNode(arr[0]); vector<TreeNode*>nodes; nodes.push_back(root); for(int i=0;i<arr.size();i++){ TreeNode * node = nodes[i]; if(2*i+1<arr.size()){ node->left = new TreeNode(arr[2*i+1]); nodes.push_back(node->left); } else{ node ->left=NULL; } if(2*i+2<arr.size()){ node->right = new TreeNode(arr[2*i+2]); nodes.push_back(node->right); } else{ node ->right=NULL; } } }

class Solution { public: Node* deleteNode(Node* head, int x) { Node* temp = head; if(x==1){ temp->next->prev = NULL; return temp->next; } int cnt =1; while(cnt<x){ cnt++;temp=temp->next; } if(temp->next==NULL){ temp->prev->next=NULL; } else{ temp->next->prev= temp->prev; temp->prev->next = temp->next; } return head; } };

code : /* Structure of the node of the linked list is as struct Node { int data; struct Node *next; Node(int x) { data = x; next = NULL; } }; */ // Function to check whether two linked lists are identical or not. bool areIdentical(struct Node *head1, struct Node *head2) { struct Node* temp1 = head1; struct Node* temp2 = head2; while(temp2!=NULL && temp1!=NULL ){ if(temp1->data!=temp2->data){ return false; } temp1 = temp1->next; temp2 = temp2->next; } if(temp1==NULL && temp2==NULL){ return true; } return false; }

code?

class Solution { public: bool is_palin(string k){ int n = k.size(); for(int i=0;i<(n/2);i++){ if(k[i]!=k[n-i-1]){ return false; } } return true; } string pattern(vector<vector<int>> &arr) { // checking rows int n = arr.size(); for(int i=0;i<n;i++){ string str; for(int j=0;j<n;j++){ str+=to_string(arr[i][j]); } if(is_palin(str)){ string ans; ans += to_string(i); ans += " R"; return ans; } } for(int j=0;j<n;j++){ string str; for(int i=0;i<n;i++){ str+= to_string(arr[i][j]); } if(is_palin(str)){ string ans; ans += to_string(j); ans += " C"; return ans; } } return to_string(-1); } };

code : bool isToepliz(vector<vector<int>>& mat) { int n = mat.size(); int m = mat[0].size(); for(int i=0;i<n-1;i++){ for(int j=0;j<m-1;j++){ if(mat[i][j]==mat[i+1][j+1]){ } else return false; } } return true; }

class Solution { public: int FindCoverage(vector<vector<int>>&matrix){ int cnt =0; int n = matrix.size(); int m = matrix[0].size(); for(int i =0 ; i < n ;i++){ for(int j =0 ; j < m;j++){ if(matrix[i][j] == 0){ if( i-1 >=0 && matrix[i-1][j] == 1) cnt++; if(i+1 < n && matrix[i+1][j] == 1) cnt++; if(j+1 <m && matrix[i][j+1] ==1 )cnt++; if(j-1 >=0 && matrix[i][j-1] ==1 ) cnt++; } } } return cnt; } };

class Solution { public: void swaps(vector<int>&arr,int a,int b){ while(a<b){ swap(arr[a],arr[b]); a++;b--; } } vector<vector<int>> rotateMatrix(int k, vector<vector<int>> mat) { int m = mat[0].size(); int n= mat.size(); k=k%m; for(int i=0;i<n;i++){ swaps(mat[i],0,k-1); swaps(mat[i],k,m-1); swaps(mat[i],0,m-1); } return mat; } };

class Solution { public: vector<int> bracketNumbers(string str) { int n = str.size(); int cnt =0; vector<int>ans; stack<int>st; for(int i =0 ; i < n ;i++){ if(str[i] == '('){ cnt++; ans.push_back(cnt); st.push(cnt); } else if(str[i] == ')'){ ans.push_back(st.top()); st.pop(); } } return ans; } };

?

code: class Solution { public: long long ExtractNumber(string sentence) { int n = sentence.size(); string largest; int maxi = INT_MIN; for(int i=0;i<n;i++){ string just; bool chk = true; while(('0'<=sentence[i] && sentence[i]<='9') && (i<n)){ just+=sentence[i]; if(sentence[i]=='9'){chk=false;} i++; } if((chk==true) && just.size()>0){ if(just.size()>0 && largest.size()==0){largest=just;} else if(stoll(just)>stoll(largest)){largest = just;} } } if(largest.size()==0)return -1; return stoll(largest); } };

class Solution { public: string compareFrac(string str) { int n = str.size(); int a1 = -1;string a; for(int i=0;i<n;i++){ if(str[i]=='/'){ a1=i; break; } a+=str[i]; } int b1 = -1;string b; for(int i=a1+1;i<n;i++){ if(str[i]==','){ b1=i; break; } b+=str[i]; } int c1 = -1;string c; for(int i=b1+1;i<n;i++){ if(str[i]==' ')continue; if(str[i]=='/'){ c1=i; break; } c+=str[i]; } string d ; for(int i=c1+1;i<n;i++){ d+=str[i]; } if(stoll(a)*stoll(d)>stoll(b)*stoll(c)){ string ans = ""; ans+=a; ans+='/'; ans+=b; return ans; } else if(stoll(a)*stoll(d)==stoll(b)*stoll(c)){ string ans = "equal"; return ans; } else{ string ans = ""; ans+=c; ans+='/'; ans+=d; return ans; } } };