วีดีโอ

Hi Bro, really good content. intuition is clear. I first tried submitting my code similar to yours 1st approach( using hashing ) but got wrong answer at 799/807. After that I submitted your code and faced the same issue. can you pls look into this.

why do you need to maintain the index in the map value when we can just maintain the minimum value by comparison at real time?

best explanation on the internet for this question but the views are so less. I also avoided your video for the last two days because of the thumbnail. I thought content wont be of very good quality but everything was perfect. so maybe put a better thumbnail from the next video... your content is already gold🙏

Sir your way of explanations is just amazing . Everything which you explains goes directly in my head and it helps me in thinking in this way. Thank you so much sir ☺☺

Nice explanation

Awesome explaination

very good explanation sir ... so happy to see this....

Why cant we just store all the prefixes in a set and have a constant time lookup in the recursive method? In that case TC would be tLen*tLen right? I did the same but it is giving me TLE. Could you please explain why?

Love your way of explanation.

bro, I've subscribed, keep doing what you are doing, your channel is literally underrated.

what a explnation sir....bhagwan kare aapke channel par 1 million subscribers ho jaye....☺😍

what if i could generate all the prefixes of given string and store it in set. Then Iterate over target checking if 1,2,3, ... lengths of prefixes are available in set. If yes, then we make reursive call for further length 1,2,3.... This also has an T^2 complexity but giving tle on 916/929? sudo code: int res = INT_MAX; string prefix; for (int j = idx; j < n; j ++) { // iterating over target string prefix += target[j]; if (st.count(prefix)) { // checking in set if prefix are available int nextRec = optimal(words, target, j + 1); if (nextRec != -1) { res = min(res, 1 + nextRec); } } else break; }

Can you do the drawing in dark mode?

we can also precompute a rolling hash using rabin karp algorithm instead of building trie time complexity will remain the same..

Can you explain about the seg tree why minimum?

Love your videos man. Thanks for all your hard work. You should definitely post these in leetcode solutions section

Thanks, really appreciate the video, though I am just starting to learn these concepts, the thought process was good to know, going to checkout the playlists in the description :)

dont pajeets poop on the street?

Your explanation is really impressive. The ideas and observations you put at every step.. its just the evidence of how a problem should be approached.

trie dp keeps giving me mle,can you tell what further optimistion is needed in my case struct Node{ Node *links[26]; bool end = false; bool containsKey(char ch) { return links[ch - 'a'] != NULL; } void put(char ch,Node* node) { links[ch - 'a'] = node; } Node* get(char ch) { return links[ch - 'a']; } bool isEnd() { return end; } void setEnd() { end = true; } }; class Trie { Node* root; public: Trie() { root = new Node(); } void insert(string word) { Node* node = root; for(int i = 0; i<word.size(); i++) { if(!node->containsKey(word[i])) { node->put(word[i],new Node()); } node = node->get(word[i]); } node->setEnd(); } bool prefix(string prefix) { Node* node = root; for(int i = 0; i<prefix.size(); i++) { if(!node->containsKey(prefix[i])) { return false; } node = node->get(prefix[i]); } return true; } }; class Solution { public: int n,m; // int dp[5005]; Trie* trie = new Trie(); int solve(vector<string>& words, string& target,int idx,vector<int>& dp) { if(idx >= n) return 0; if(dp[idx]!=-1) return dp[idx]; int res = 1e9; for(int i = idx; i<n; i++) { string temp = target.substr(idx,i-idx+1); if(trie->prefix(temp)) res = min(res,1+solve(words,target,i+1,dp)); } return dp[idx] = res; } int minValidStrings(vector<string>& words, string target) { m = words.size(); n = target.size(); for(int i = 0; i<m; i++) trie->insert(words[i]); // memset(dp,-1,sizeof dp); vector<int> dp(n+1,-1); int res = solve(words,target,0,dp); return res == 1e9 ? -1 : res; } };

thanks for making credible editorials.

Great Solution...

getting tle with the approach of 3 problem using recursion + memo+trie, please look into my solution

class Solution { HashMap<String, Boolean> map=new HashMap(); class TrieNode { TrieNode[] children; boolean isEndOfWord; public TrieNode() { children = new TrieNode[26]; isEndOfWord = false; } } public void insert(String word, TrieNode root) { TrieNode node = root; for (char c : word.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { node.children[index] = new TrieNode(); } node = node.children[index]; } node.isEndOfWord = true; } public boolean findWordsWithPrefix(String prefix, TrieNode root) { TrieNode node = root; int result=0; for (char c : prefix.toCharArray()) { int index = c - 'a'; if (node.children[index] == null) { return false; // No match for the prefix } else result++; node = node.children[index]; } return true; } public int find(String s, TrieNode root, HashMap<Integer , Integer> memo, int index, int n){ // System.out.println(s); // int n1=s.length(); if(index==n) return 0; if(memo.containsKey(index)) return memo.get(index); boolean found=false; int x=10000000; String temp=""; for(int i=index;i<s.length();i++){ temp+=s.charAt(i); boolean cnt=false; if(map.containsKey(temp)) cnt=map.get(temp); else { cnt=findWordsWithPrefix(temp, root); map.put(temp, cnt); } if(cnt) { // System.out.println(s+" temp: "+temp+" "+" child: "); int child=find(s, root, memo, i+1, n); if(child!=-1){ x=Math.min(x,child ); found=true; } } else break; } if(!found){ memo.put(index,-1); return -1; } memo.put(index,x+1); return x+1; } public int minValidStrings(String[] words, String target) { int n=words.length; TrieNode root=new TrieNode(); for(int i=0;i<n;i++){ insert(words[i], root); } HashMap<Integer, Integer> memo=new HashMap<>(); return find(target, root, memo, 0, target.length()); } }

Still getting TLE. 916/929 :((((

Can u post solutions yesterday's biweekly contests hard questions?

Please try to upload yesterday biweekly contest 3rd problem 🙏

Great explaination ❤. The z function approach is really understandable .

class Solution { public: vector<vector<int>> memo; int rec(int i, int mask, vector<vector<int>>& grid) { if (i == grid.size()) return 0; if (memo[i][mask] != -1) return memo[i][mask]; int mxscore = rec(i + 1, mask, grid); for (int j = 0; j < grid[0].size(); j++) { if ((mask & (1 << grid[i][j])) == 0) { mask = mask | (1 << grid[i][j]); mxscore = max(mxscore, grid[i][j] + rec(i + 1, mask, grid)); mask = mask ^ (1 << grid[i][j]); } } return memo[i][mask] = mxscore; } int maxScore(vector<vector<int>>& grid) { int m = grid.size(); memo.assign(m, vector<int>(1 << 10, -1)); return rec(0, 0, grid); } }; can anyone please help me why this solution is not working

Thank you for the clear explanation.

Thanks for the awesome tutorials. And thanks for 2 solutions here

Wish you explained the Combinations solution as well

Hi please change videos in playlists from newest to oldest . Its a request

Khuch bhi samjh nhi aya mirror image bhi nhi 😭

amazing explaination. Thank You ❤❤❤

This channel is such a hidden gem that if anyone just randomly follow any playlist of him will be master of it . Just do it you will be +500 rated everywhere if you are pupil,specialist even expert

Last taken is position of 22:22 knight❤

Sir whats wrong with my approach struggling since morning class Solution { public: vector<int> dx = {-2, -2, -1, -1, 1, 1, 2, 2}; vector<int> dy = {-1, 1, -2, 2, -2, 2, -1, 1}; int helper(int kx, int ky, pair<int, int> pyaada, vector<vector<int>>& visited, vector<vector<int>>& dp) { if (kx == pyaada.first && ky == pyaada.second) { return 0; } if (kx < 0 || kx >= 50 || ky < 0 || ky >= 50) return 1e9; if (dp[kx][ky] != -1) return dp[kx][ky]; int mini = 1e9; if (visited[kx][ky] == 1) return 1e9; visited[kx][ky] = 1; for (int i = 0; i < 8; i++) { int answer = 1 + helper(kx + dx[i], ky + dy[i], pyaada, visited, dp); mini = min(mini, answer); } visited[kx][ky] = 0; return dp[kx][ky] = mini; } int getMinMoves(int kx,int ky ,pair<int,int> pyaada) { vector<vector<int>> visited(50,vector<int>(50,-1)); vector<vector<int>> dp(50,vector<int>(50,-1)); return helper(kx,ky,pyaada,visited,dp); } int maxMoves(int kx, int ky, vector<vector<int>>& positions) { bool aliceTurn = true; int score = 0; set<pair<int,int>> pyaadePositions; for(auto itr :positions) { pyaadePositions.insert({itr[0],itr[1]}); } while(pyaadePositions.size() >0 ) { int currentMinMoves =1e9; int currentMaxMoves =0; pair<int,int> minPyaada,maxPyaada; for(auto position:pyaadePositions) { int val = getMinMoves(kx,ky,position); if(val >currentMaxMoves) { currentMaxMoves = val; maxPyaada = position; } if(val<currentMinMoves) { currentMinMoves = val; minPyaada = position; } } if(aliceTurn) { score += currentMaxMoves; kx = maxPyaada.first; ky = maxPyaada.second; pyaadePositions.erase(maxPyaada); } else { score+= currentMinMoves; kx = minPyaada.first; ky = minPyaada.second; pyaadePositions.erase(minPyaada); } aliceTurn = !aliceTurn; } return score; } };

For finding the minimum distance you can use indexes of the pawns array in a 2D matrix of size N*N, where distance[i][j] represents shortest distance to reach from pawn at index i to pawn at index j(where N is the size of pawns array,) and for every index you calculate the shortest distance to every other cell which can be done in 50*50 for a single Pawn and for N pawns it boils down to 50*50*N (here N <= 15). And to check whether or not a given (x,y) represents a pawn we can use a hash map where each pawn is mapped to its index in pawns array

please do video for q.2 and q.3 also

I was very close, coded out bitmask dp all the way. Got WA tho :( Thankyou for this

Best explanation i could find ! thankyou. Keep up the good work..

first half of the video was okay, next half felt like you were trying to convince yourself. Please take it as a constructive criticism, it really means a lot for people like us who are tying to upsolve. Your videos are indeed helpful.

Great Explanation Sir

very nice solution sir thanku so much

Its pronounced as Ex-OR

i am unable to find where my code is wrong can u please fix my code Output [10,10,10] Expected [6,10,7] *** from typing import List from bisect import bisect_left class segment: def __init__(self,arr): self.n = len(arr) self.seg = [None]*(4*self.n) self.build(0,0,self.n-1,arr) def build(self,i,l,r,v): if l == r: self.seg[i] = [[v[l][1],v[l][0]+v[l][1]]] return mid = (l+r)//2 self.build(2*i+1,l,mid,v) self.build(2*i+2,mid+1,r,v) self.seg[i] = self.merge(self.seg[2*i+1],self.seg[2*i+2]) def merge(self,s1,s2): l = len(s1) l1 = len(s2) c = [None]*(l+l1) i,j,k = 0,0,0 while i < l and j < l1: if s1[i] < s2[j]: c[k] = s1[i] i += 1 k += 1 else: c[k] = s2[j] j += 1 k += 1 while i < l: c[k] = s1[i] k+= 1 i+= 1 while j < l1: c[k] = s2[j] j += 1 k += 1 for i in range(len(c)-2,-1,-1): c[i][1] = max(c[i][1],c[i+1][1]) return c def query(self,l,r,low,high,y,i): if low > r or high < l: return -1 if low >= l and high <= r: arr = self.seg[i] ind = bisect.bisect_left(arr,[y,-1]) print(ind) if ind == len(arr): return -1 return arr[ind][1] mid = (low+ high)//2 left = self.query(l,r,low,mid,y,2*i+1) right = self.query(l,r,mid+1,high,y,2*i+2) return max(left,right) class Solution: def maximumSumQueries(self, A: List[int], B: List[int], Q: List[List[int]]) -> List[int]: n = len(A) m = len(Q) ans = [] v = list(zip(A, B)) v.sort() mt = segment(v) for x, y in Q: l = bisect_left(v, (x, -1)) print(l) print(mt.seg) print(l,n-1) res = mt.query(l,n-1,0,n-1,y,0) ans.append(res) return ans ***

Thanks alot for the amazing editorial, mai apke channel ko bahot pehle se follow kar rha hu, and apke editorial ki ek sabse khash baat hai ki, ki aakhir sochana kaise hai, solution tak kaise pahoche ye sikhane ko milta ho, Thanks alot for the amazing editorials.

Bro great please change the color of your cursor. It is not visible when seen from mobile.

happy teachers day bhaiya. Thank you for giving such quality vidios for free. we will always be grateful to you.