Awesome! One thing that stands you out of other youtubers is that you explain the solutions with 'intuitions' and compare between different possible solutions, rather than just diving into the solution. It's not about the solution but the approach the we need to learn by solving these problems. This gives us more understanding & confidence to approach similar problems. Thank you for the effort and time!

@techdose4u

4 жыл бұрын

Welcome :)

When I find a solution video by Tech Dose, I know I am saved.

@techdose4u

3 жыл бұрын

😂 Nice ♥️

@arpitsatnalika

3 жыл бұрын

Same

Trie is such a pain to implement but very easy to understand

@techdose4u

4 жыл бұрын

😅

@AGENTxxFURY

3 жыл бұрын

True bro ..... :)

The best channel for DSA . Great job , surya !

Sir, I usually watch nick white or other yt-ber they tell soln with 10-15 min, but you focus on concept , that is making you stand out keep doing it.. cover all possible topics. Thank You

@techdose4u

3 жыл бұрын

Welcome :)

Thank you for all the approaches much needed to develop the thought process 👍 Great job👌

@techdose4u

4 жыл бұрын

Welcome :)

You made it super simple. Hats off & thank you for such an explanation ❤

I guess the DFS+Map approach has exponential complexity since we're branching into 4 and checking all other branches if the current branch is not a match. I guess it should be exponential, not O(nm*nm*num_of_words). While calculating the complexity for the worst case, the other branches weren't considered in your example. Anyway, the explanation is great, Thank you for the awesome video!

@techdose4u

4 жыл бұрын

Complexity can be 3^NM because every cell will have 3 options in best case.

@Rishit.Chaudhary

4 жыл бұрын

@@techdose4u But that would mean that the DFS with Trie approach is also exponential, because even there during DFS, every cell will have 3 options at best.

speciall thing about your channel is you always explain time and space complexity in detail.. specially visited to this video for time and space analysis :)

@techdose4u

3 жыл бұрын

Nice :)

You are doing an awesome job bro!! keep it up the good work!

@techdose4u

3 жыл бұрын

Thanks

Thank you sir. Your videos helped me to complete june challenge. Thank you for existing ♥️

@techdose4u

4 жыл бұрын

Welcome :)

amazing explanation

Sir I salute you for your efforts in the Leetcode challenges over the last three months. You are Soo awesome! Really really excited and looking forward to the topic-wise videos.

@techdose4u

4 жыл бұрын

😁

In the dfs + hashmap or just dfs approach, why we would even check if the string length is > than row*col since it could not be accommodated in the matrix anyway.

What is the time complexity in the DFS approach and DFS+trie ?

How does trie approach handle if words = [agile, age] both starting with "ag"?

Best video for this problem. Keep doing the good work bro. Please try explaining Java solutions also

@techdose4u

3 жыл бұрын

Thanks 😊 I will try java soon 😅

What is the time and space complexity of the Trie & HashMap approach?

Thanks for sharing this problem in easy way to understand 😊😇..

@techdose4u

4 жыл бұрын

Welcome

This video is quite helpfull 🙏🙏 thank you sir for making such contents

@techdose4u

4 жыл бұрын

Welcome :)

I think the time complexity for DFS + HashMap is O(# words) * O(MN) (starting point) * O(2 ^ MN) (this part is my guessing) For example: dict = [tatatatatatatatatatatatata] (repeat 'ta' long enough so that we cannot find this word in this 2D board) t a t a t a t a t a t a t a t a t a t a In this example, there are (MN / 2) the starting points. And for every starting point, we can either go up or down or left or right but I think it will generally have two branches when we traverse by DFS.

@rahulbhardwaj4380

Жыл бұрын

the 2 in the 2^MN can be ambiguous over the matrix (for different cases) but i also agree that this would go to an exponential with a power of MN.

In the time complexity even if we have more number of words our search will stop at length equal to board length in the trie right? In that case shouldnt the time complexity be O(mn*mn) alone

Thank you for TRIE solution, it is really helpful ! I have one doubt , in worst case of DFS+ HashMap Approach we can reduce complexity by checking if length of string to be searched > size of grid (m*n) even we can maintain the $count variable if in any search it $count == m*n , no need to check for rest of the position in the hashmap Please verify my approach..

Thanks for the great tutorial. which device are you using for writing? could u please share the link?

Thank you so much such a good explanation sir

@techdose4u

4 жыл бұрын

Welcome

Your videos are just owsm sir..👍👍

@techdose4u

3 жыл бұрын

Thanks :)

i think we can improve upon the space complexity of trie using a map instead of *child[26] because we are mostly not using all the 26 letters i guess

Sir will be eagerly waiting for your new videos! A bit sad for not getting July challenge videos anymore but even more excited to learn topics like graphs and DP from you. My suggestion for new videos: 1 video from DP/Graph and 1 from Subjects. Expecting great content of Subject's videos just like all other videos of yours. Thanks a lot!!

@techdose4u

4 жыл бұрын

Subject in the sense? I will try to put 1 video per 3 days on graph.

@abhishekgautam1063

4 жыл бұрын

@@techdose4u subjects like OS, DBMS, Oops, System Design. And maybe just frequently asked questions from these subjects.

@techdose4u

4 жыл бұрын

I will put theory MCQs with solutions on my website starting this weekend.So, that should give a good practice in a short time. Later you can revise the quizzes to cover the syllabus before interview quickly.

@abhishekgautam1063

4 жыл бұрын

@@techdose4u that's really great sir! Thank You :)

@techdose4u

4 жыл бұрын

Welcome

I didn't get why using trie is an improvement over pruning using hashmap , someone please explain

Very well explained!

@techdose4u

4 жыл бұрын

Thanks :)

Why for hashmap approach time complexity is O(mn* mn * no of words) .. Should not it be O(mn * no of words.). We are traversing whole grid (m*n) for all the words. Can someone please explain

Where can I see the solution which uses DFS + hashmap?

DFS + MAP -> fails to pass test case No 34 (TLE).

@techdose4u

4 жыл бұрын

:( This must be because of exponential time.

@anmolwadali9227

4 жыл бұрын

same situation happens with me

@thiyagarajanr225

4 жыл бұрын

I am able to pass!

Upvoting for explaining worst time complexity.

In worst case hashmap+dfs has same complexity as dfs+trie?

I think the worst case time-complexity of dfs+hashMap soln is - No. of words*NM*4^(size of word).... The exponential factor is due to 4 recusive calls up, down, top, bottom. Correct me if I am wrong.

Thanks for the great tutorial Tech Dose . Your videos are awesome. I have 2 doubts : 1) Isn't the time complexity of the dfs + trie approach is O(MN * 4 ^ (max word length)) ? 2) I think while doing the dfs with the help of trie, we can calculate the word on the fly to store it . Storing the word in trienode is wasting spaces.

@mohammadmoaddi2268

2 жыл бұрын

I think for the first case, 4^maxwordlen is at most MN right?

@mohammadmoaddi2268

2 жыл бұрын

Because of visited or $

Sir, what if we include hash map with trie ?... At each new element in Trie, u were iterating through the entire matrix But, instead of iterating, u could just fetch the trie element's next coordinate from the hash map. This approach will be difficult to code.

@techdose4u

4 жыл бұрын

No. DFS + TRIE is enough. No need for map because we are iterating for all cells on board but we are searching for all words at once whether any word can start from given cell or not while in DFS only, we were traversing the board separately for each word. So map can help in DFS but not with trie.

At first I have tried with DFS + Map as soon as seen your video looking at worst case,I thought trie would be a better option

@techdose4u

4 жыл бұрын

😅

we will do dfs call from each cell and constrcuct the word appending chars one by one. Then we will check if newly constructed word is present in hashmap or not if yes, we will increase count and remove that word from map. Time comp will be O(nm * nm) , space complexity O(no. of words). Isn't it possible? sir

We can ignore a word in the dictionary if its length is greater than N*M

Time complexity is m * n * 4 ^ (max_length_of_string). 1) We can start searching word from any position from m * n positions. 2) From each position , we can go in 4 directions each.

could you please make the video for leetcode problem 126 word ladder ii.

In the worst case example you have given, for each letter in the word we have n*m choices at max so I think the time complexity will be (no. of words)*(number of letters)^n*m. Correct me if I am wrong... Any way very very good explanation.. Thank you soo much sir..

@techdose4u

4 жыл бұрын

It can be 3^NM because every cell will have 3 options in best case and it can cover the entire cells so this will form a ternary tree structure. We have 3 choices at each cell and not NM.

Can you tell me what does the fastio method means?

@techdose4u

4 жыл бұрын

Turns off the sync for C++ with C standard streams and hence improves input and output time.

I wonder what'll be the output for Board=[a,a a,a] Dict={aa} I think it would be [aa,aa,aa,aa,aa,aa,aa,aa] Trie structure : (/) / a / a ends=1 String="aa" When we start doing dfs Starting with(0,0) it will output ["aa","aa"]irrespective of checking whether the string has already printed. Same thing happens with starting with (0,1),(1,0),(1,1) by printing total of 8 times of "aa".

@techdose4u

4 жыл бұрын

You can use a SET to remove duplicates.

Can you please explain the time complexity of both the solutions?

@techdose4u

4 жыл бұрын

Every cell has 3 options at max, we are branching like a ternary tree and hence time will be NM×3^NM.

Its a nice explanation,but always trie is a headache or me...

@techdose4u

4 жыл бұрын

I can understand :)

So, Sir you are going to start with Graph tutorial videos from today ??

@techdose4u

4 жыл бұрын

Expect 1 video per 3 days.

I believe the time complexity shown in the video is incorrect. The time complexity should be O(nm * 4 ^(word length) * word length) because the dfs portion should take 4^(word length) time Here is my analysis: So the dfs function will run up to 4 more dfs in the worst case scenario with each of the dfs having to visit one less cell (we can represent the number of cells left to visit with the variable X) So we can represent the complexity of the dfs function as: f(x) = f(x-1) + f(x-1) + f(x-1) + f(x-1) -> 4f(x-1) and f(1) = constant time f(x) -> 4 * 4 * ...(continues x-1 times)... * 4 + constant time = 4^(x-1) - > 4^(x) Here we only need to visit up to word length cells so we can say x here equal word length. Given this we get a worst case complexity of O(nm * 4^(word length) * word length)

I don't think hashmap will be much of an improvement, cause to create a hashmap, anyways you'll have to iterate the whole 2d array to store the position in map.

Started graph on 27 june and till now i have learnt how to understand editorial's code Pata nhi chal raha kaise karu😞

@techdose4u

4 жыл бұрын

😅Aajse video aa rha hai....dekhna aur practice krna shuru krdo :)

Sir may I ask what is the time and space complexity for leetcode 79 word search I ? It's always hard for me to analyze time complexity for recursion and backtracking.

@techdose4u

3 жыл бұрын

Hmmm....Have I made a video on it ?

@yitingg7942

3 жыл бұрын

@@techdose4u No you haven't, I did it though, but I don't know about time complexity.

@techdose4u

3 жыл бұрын

Then I will solve it and let you know :)

Hi Can you please try solving divide chocolate question from leetcode .

@techdose4u

4 жыл бұрын

I will try but I can't put video for that now 😅

Please upload solution for egg dropping problem using dynamic programming......

@techdose4u

4 жыл бұрын

Okay. I will try

The time Complexity you calculated is wrong. It will be O(N*M*3^length of word) not (N*M*N*M*length of word)

In the first approach , should not the time complexity be O(N*M. *. 4^10. *. No of words

Nice video, I think the time complexity is incorrect though !

@GaneshSatputeAtPlus

3 жыл бұрын

You should've mentioned why you think that way

@gabrieldjebbar7098

3 жыл бұрын

You are right, sorry. I think what we are doing is actually using backtracking and not a dfs (we visit several time the cells of the board for a given starting cell). Time complexity should therefore be expotential.

@GaneshSatputeAtPlus

3 жыл бұрын

I initially thought the same. But as I thought bit more, as we're not visiting the same node again and again, we will be visiting each node only once in case of the example with matrix filled with a's and search string also being a's. In this case, we will be traversing each cell of matrix before we exit. So the total complexity would be n * m, unlike what our intuition says.

My DFS + HM will not pass

@techdose4u

4 жыл бұрын

How? It is similar to trie method.

@sumengwang8918

4 жыл бұрын

@@techdose4u It fails at the all 'a's case. I also used your method of replacing char with dollar to check if visited. So it shouldn't have any other redundant runtime.

@techdose4u

4 жыл бұрын

I did not try this method but yea, for all a's the time will largely differ. The hint itself mentions to implement trie. Better to use what I explained 😅

20:04

I think there is an error in the explanation of the code... Extra space is being used for holding the original value of the cell before replacing it with the '$' symbol, it is not constant space. 🤔 The reason is that in every function call, you are creating a variable called: ch, to hold the original value of the cell, before replacing it with the '$' symbol. In the worst-case scenario you will be exploring the entire board during DFS and it that case the number of function calls in the call stack, will be equal to the number of cells in the board. As you have one ch variable per function call, the number of ch variables created by the program would be equal to the number of cells in the board, so effectively, you have not saved any space as compared to creating a special visited array. The only improvement in terms of space is that your average space usage is better with ch as compared to using a visited array, but in cases where you will be visiting all the cells in the board, even if it's just once during DFS, then there is no benefit of using ch over a special visited array. Otherwise great video! Would be interesting to build an STL container for Tries to make such questions easier, but that's for later... 😅

@Mauglus

4 жыл бұрын

You already have the word with current index, so you dont need to define an extra variable

@techdose4u

4 жыл бұрын

You can simply make this 0(1) by adding a const integer overflowing z and then subtract the same integer. Use macro for this. This will be absolute 0(1).

@techdose4u

4 жыл бұрын

You are counting that tiny space!! One node of tried can consume hundreds of such chars :(

@Rishit.Chaudhary

4 жыл бұрын

@@techdose4u After the video I spent some time to verify if I understood the algorithm, and check if it could be made better.😅 That's when I realized that the usage of ch was not saving any space. Hence I just wanted to point that out because in the video it was incorrectly mentioned.🙌 But I do agree that compared to the Trie data structure we created, the extra space taken for ch or a visited array is not much in comparison.🤔

i dont think time complexity is right

//No need to use hashmap just for comparing the first char //see below code class Solution { public List findWords(char[][] board, String[] words) { ArrayList ans = new ArrayList(); for(String ele : words) { for(int i=0;i

Using your idea, but in Java. ``` class Solution { class Trie{ char c; boolean word = false; String w; Map children = new HashMap(); } void add(String s){ Trie dummy = root; for(char c: s.toCharArray()){ if(!dummy.children.containsKey(c)){ dummy.children.put(c, new Trie()); } dummy = dummy.children.get(c); } dummy.word = true; dummy.w = s; } Trie root = new Trie(); public List findWords(char[][] board, String[] words) { root.c = '*'; for(String w: words) add(w); Set result = new HashSet(); for(int i=0; i= board[0].length) return; if(!trie.children.containsKey(board[i][j])) return; trie = trie.children.get(board[i][j]); if(trie.word) list.add(trie.w); char temp = board[i][j]; board[i][j] = '*'; for(int[] c: coord){ backtrack(list, board, trie, i+c[0], j+c[1]); } board[i][j] = temp; } } ```

@techdose4u

4 жыл бұрын

👍

Amazing !!! You are god of DSA 🔥🔥🔥 ... Thank you very much for making this unique and valuable video on yt ! Edit:- I have been trying this solution using tries for some time and I have come to a solution --> ... but the problem is that it still is giving a TLE. If you get time, can you please see what optimization more I need to do in this ? Code :- class Node { public: char val; unordered_map children; string word; bool isWord, done; Node* parent; Node(char v) { val=v; isWord=false; parent=NULL; done=false; } bool hasChild(char v) { if( children.find(v)==children.end() ) return false; return true; } // done Node* getChild(char v) { return children.at(v); } void insert(char v, Node* child) { child->parent=this; children.insert( {v, child} ); } void setWord(string w) { isWord=true; word=w; } void display() { // display the word if(isWord) { coutchildren.size()val; par=par->parent; } par->children.erase(v); cout