Word Search | In Depth Explanation | Apple | Amazon | Microsoft | codestorywithMIK

This is our 1st Video on our Backtracking Playlist.
In this video we will try to solve a very Popular and a classical Backtracking Problem "Word Search".
Share your learnings on LinkedIn, Twitter (X), Instagram, Facebook(Meta) with hashtag hashtag#codestorywithmik & feel free to tag me.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Word Search
Company Tags : Apple, Amazon, Microsoft, Intuit
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/word-se...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview #interviewtips
#interviewpreparation #interview_ds_algo #hinglish

[@vaibhavsrivastava7451]

Ahh man you deserve more respect ......thank u so much i always want to hear your voice while understanding leetcode explanation .

[@codestorywithMIK]

Thanks a lot Vaibhav. Really appreciate your kind words. Made my day ❤️❤️❤️ Share it with your friends 😇❤️

[@deepakdass4710]

I tried to solved it by myself. As I have been following your content from a long time. I have learnt how to approach to solve a problem. I started by drawing recursion tree and then backtracking. Also putting checks to avoid unnecessary conditions. I was able to solve it by myself. And then I watched this video. Thank you Sir 🎉😊

[@souravjoshi2293]

Hey man, heartful thanks to you. Your soothing voice makes us stick to your video Thanks again for today's code

[@karnikasingh9140]

Thanks MIK for such for such good explainations!! Here is the java code for same- class Solution { int m; int n; int[][] directions= {{1,0},{-1,0},{0,1},{0,-1}}; public boolean exist(char[][] board, String word) { m = board.length; n = board[0].length; for(int i =0;i

[@EB-ot8uu]

finest explanation

[@killeraloo3247]

Bhai mast samjhaya, sab samajh aa gya.

[@gui-codes]

all my doubts are gone. thank you so much.

[@user-ub2is4rs4x]

No one can beat this level of explanation. You deserve more visibility

[@pragatigoyal4015]

Your way of explanations is really good, whatever question you explain i dont need to see the code for that i can write my own. Can you make a separate playlist on different approach we use in DSA program and tricks to identify those. It will be easy to follow that playlist if we are having interview

[@wearevacationuncoverers]

masterpiece

[@girikgarg8]

Nice explanation

[@aws_handles]

too good

[@nagmakhan672]

Thanks

[@ananyabhardwaj1861]

please make videos for questions in lover babbar sheet, as I searched through youtube for many questions and I didn't get a good videos like yours .

[@qR7pK9sJ2t]

Really very good way of explaining ! Simply awesome !

[@codestorywithMIK]

Thanks a lot! 😇❤️🙏

[@bhuppidhamii]

Follow up: Could you use search pruning to make your solution faster with a larger board? what does this means?

[@AnandKumar-kz3ls]

Space Complexity: O(L) Time Complexity: O(M * N * 3^L) Space Complexity is because of recursion - to store function stack context. Time Complexity - from every block we go in three adjacent blocks (avoiding the direction we came from). This walk can go for max of L times. So each thred at most goes L length long. -> O(3^L). Now this is applied at each node from main calling function -> O(M * N). Therefore, O(M * N * 3^L).

[@codestorywithMIK]

I’ll ensure to mention TC in the video from next time. Thanks Anand ❤️

[@anushkathakur6531]

why are we avoiding the direction we came from? in the sample example if the word was FSA then in 2nd row and 2nd col we would have found F and then we would have 4 options for finding S (left,up,right,down) ??

[@bhuppidhamii]

can you explain the SC?

[@pulastyadas3351]

your explanation is like butter :)

[@codestorywithMIK]

Means a lot. Thank you for watching 😇🙏

[@devmadaan5146]

Leetcode daily 😁, kya haal chal vaise😂

[@suchibansal78]

very well explained

[@codestorywithMIK]

Thanks a lot Suchi 😊

[@user-fe6uu5gn7h]

Brother your way of explanation damn too good you should start teaching dsa and cover all topics from scratch

[@codestorywithMIK]

It means a lot to me 🙏🙏❤️❤️ Soon I will start

[@KishoreKumar-rh2tw]

thanku bhiya,sabse acha aap hi padhate ho.

[@codestorywithMIK]

Thank you so much Kishore ❤️❤️

[@KishoreKumar-rh2tw]

Bhaiya Nqueen problem pr bhi ek video please,sbka dekhliya nhi smjh aarha

[@abhijitroy1958]

The mark condition in 2nd line of find function I guess lf no use right. Cause we are changing right after the true returns

[@sujalgupta6100]

what about the follow up which says to prune ?

[@kristinabarooah3163]

which notes app are you using?

[@jagadeeshp1163]

HI Mik one doubt when should we write x+solve(....) and when to take x as a parameter like solve(x) how to identify this and i am confused some times we write val+rec() call and sometimes we take val in the rec() call what is the difference please help me out hope you understand my point

[@jagadeeshp1163]

Respect++ great lecture

[@codestorywithMIK]

Thank you so much 😇🙏❤️

[@jagadeeshp1163]

can i get a 1-1 session

[@codestorywithMIK]

@jagadeeshp1163 sure. You can find the link for session in my Github repo - github.com/MAZHARMIK

[@syedhamzashah3803]

Which playlist should I follow to get started from the very beginning? Like you didn't explain directions in this video so which one should I refer to?

[@priyanshugoutam1223]

bhaiya aapko concept smjhana aata hai mai dekh chuka ye ....meri aapse request hai if possible please man lena ...aap kisi bhi language me dsa ka course start kardo proper youtube pe hi...i know starting me utne views nahi aate hai but koi bhi dekhega to suggest zrur karega bhaiya please

[@codestorywithMIK]

Hi Priyanshu. Thanks for your feedback. I will definitely look for this possible Thanks a lot ❤️❤️❤️

[@priyanshugoutam1223]

@@codestorywithMIK thank you bhaiya

[@souravjoshi2293]

Yessss

[@vivek.tiwary]

What would be time complexity ?

[@justlc7]

Can you please also explain time and space of this?

[@ankitsourav1217]

Bro ek bootcamp lelo, jahan par we can solve good leetcode questions. It will help so much in placements.

[@codestorywithMIK]

Sure Ankit. I have this plan in my queue. Will soon plan it. Thank you so much for your input ❤️❤️❤️

[@Ash-fo4qs]

video request : leetcode 39,40,216,377

[@sujansinhthakor2314]

Can we solve this problem using BFS?

[@devshubham5528]

I am getting TLE with same code on leetcode, what should I do? ( it's exactly same code)

[@devshubham5528]

resolved when I removed loop on directions and manually called the find function

[@rudrabhingradiya]

sir i'm new in your channel and starting video from directly backtracking so i didn't get the topic of direction {1,0},{-1,0}{0,1}{0,-1} so can you tell in which video you had explained it already so i can watch please reply

[@codestorywithMIK]

Hey. Actually it's difficult to find the exact video as there are many videos.So let me try to explain and make it simple here : In problems involving depth-first search (DFS) or breadth-first search (BFS), it's common to explore neighboring cells in a grid or graph. The directions array you mentioned is a convenient way to represent the possible movements in terms of changes in the row (i) and column (j) indices. Here's a breakdown : 1) Defining Directions Array: directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; This array contains four pairs of numbers, each representing a direction to move in a 2D grid. The pairs are {1, 0} (down), {-1, 0} (up), {0, 1} (right), and {0, -1} (left). 2) Using Directions Array in a Loop: for(auto &dir : directions) { new_i = i + dir[0]; new_j = j + dir[1]; } In this loop, they iterate over each direction represented by the pairs in the directions array. For each direction, they calculate the new row index (new_i) and column index (new_j) by adding the corresponding values from the direction pair to the current indices (i and j). new_i = i + dir[0] calculates the new row index. new_j = j + dir[1] calculates the new column index. By using this loop with the directions array, you can easily explore adjacent cells from a given cell (i, j) without explicitly writing separate code for each direction. This is particularly useful in grid-based problems where you need to traverse neighboring cells during DFS or BFS. Hope this helps.

[@user-ub2is4rs4x]

@@codestorywithMIKthanks ❤

[@YashSinghal]

wow. what will be the time complexity of the soln??

[@codestorywithMIK]

Hi Yash, The time complexity will be O(m*n*3^L) Where L = length of input word Because in worst case we will visit each cell (m*n) and from each cell our recursion depth will go as far 3^L Why not 4^L Because, we never visit the path where we came from. (If you draw the backtracking/recursion tree, you will notice at any level, 3 Children are allowed since we cannot traverse back to oath from where we came)

[@souravjoshi2293]

O(m*n*3^K), where K = length of word

[@user-ti7jb6xp4n]

Bhaiya when we are writting direction inside find() giving TLE why can someone please help

[@devshubham5528]

remove loop on directions and manually called the find function if( find(board,word,i-1,j,ind+1) ) return true; if( find(board,word,i+1,j,ind+1) ) return true; if( find(board,word,i,j-1,ind+1) ) return true; if( find(board,word,i,j+1,ind+1) ) return true;

[@kushaalrana]

When I write the last if condition in the same if where we are returning false I am getting TLE. Anyone why? This condition in the 2nd if If(board[i][j]!=word[ind]) return false;

[@SanjaySingh-xw3mi]

Can you please show your whole code then the problem can be identify

[@kushaalrana]

I understood the problem, actually the problem was i didn't not add & in the for loop But what's the difference between For(auto &dir: direction) Vs For(auto dir: direction)

[@it047_prakhar8]

jo sabse last wali line m return false kia uski need kya thi wo samajh nhi aaya

[@acceleratorlevel645]

It means we have exhausted all possibilities and still haven't seen the word in the matrix, so this means the word doesn't exist,so we return false.

[@aditigupta6870]

Time complexities explanation is missing in all videos

[@codestorywithMIK]

Yes in old videos, I missed the discussion of TC and SC. In new videos i add explanation of time and space

[@aditigupta6870]

Can you explain the time complexity here mik? I mean in this word search problem

[@subhamcoder]

sir isme deadlysignal bol raha haiii bool f(int i,int j,int n,int m,string &s,vector& b, string word){ if(i=m)return 0; if(s==word)return 1; s.push_back(b[i][j]); if(f(i+1,j,n,m,s,b,word)==1)return 1; if(f(i-1,j,n,m,s,b,word)==1)return 1; if(f(i,j+1,n,m,s,b,word)==1)return 1; if(f(i,j-1,n,m,s,b,word)==1)return 1; return 0; }

[@nish0798]

codestorywithMIK bhai ye code mein only 18 test cases hi pass ho rahe hai aisa kya class Solution { public boolean exist(char[][] board, String word) { boolean[][]vis=new boolean[board.length][board[0].length]; String ans=""; char startchar=word.charAt(0); for(int i=0;i

[@anshugupta2340]

Bro your explanation is damn good!! bro can you help me in finding out whats wrong in the below code. int l,n,m; vectordirections{{0,1},{0,-1},{1,0},{-1,0}}; bool findAll(vector& board, int i,int j,int ind,string&word){ if(ind>=l)return true; if(i=n||j=m||board[i][j]!=word[ind])return false; char temp=board[i][j]; board[i][j]='$'; for(auto &dekh:directions){ int new_i=i+dekh[0]; int new_j=j+dekh[1]; if(findAll(board,new_i,new_j,ind+1,word)); return true; } board[i][j]=temp; return false; } bool isWordExist(vector& board, string word) { n=board.size(); m=board[0].size(); l=word.length(); for(int i=0;i

[@gurnoorchhabranit-jalandha5002]

remove semicolon after if conditions

[@molyoxide8358]

Bro pls check this code. It's not working class Solution { public: int m=0,n=0; bool backtrack(vector& board, string &word, int i, int j, int idx) { if(idx == word.size()) return true; if(i>=m || j>=n || i

[@AJ-xc3ks]

Bro u are calling for all the char of board Firstly check that 1st char of word and board ele match then call

[@molyoxide8358]

@@AJ-xc3ks Didn't understand It's been 5 months since this problem can you pls point it out.

[@ssplusultra8645]

if anyone is wondering, leetcode pro'lly updated the test cases and this implementation gives TLE now. we can do something like this instead of using directions and for loop: ``` bool searchWord(vector& board, int i, int j, int k, string &word){ if(k==word.size()) return true; if(i=m|| board[i][j]=='$'){ return false; } if(board[i][j]!=word[k]) return false; char temp = board[i][j]; board[i][j] = '$'; bool ret = searchWord(board, i-1, j, k+1, word) || searchWord(board, i+1, j, k+1, word) || searchWord(board, i, j-1, k+1, word) || searchWord(board, i, j+1, k+1, word); board[i][j] = temp; return ret; } ```

[@abhinav7622]

thanks bro !!!

[@aditigupta6870]

Hi sir, whats wrong here? It fails 13 test cases including 1 example test case with word SEE: class Solution { int m,n; int[] dx={-1,1,0,0}; int[] dy={0,0,-1,1}; int i_,j_,k; public boolean isPresent(char[][] board,int i,int j,String word,int ind){ if(ind==word.length())return true; if(i

[@kashifrahman]

I can't understand the direction vector 🥲

[@kamranwarsi12b22]

class Solution { public: bool solve(int i, int j, int n, int m, vector& board, string &word, int k){ if(k==word.size()){ return true; } if(i=m || board[i][j]!=word[k]){ return false; } char ch = board[i][j]; board[i][j] = '#'; bool op1 = solve(i+1,j,n,m,board,word,k+1); //down bool op2 = solve(i-1,j,n,m,board,word,k+1); //up bool op3 = solve(i,j+1,n,m,board,word,k+1); //right bool op4 = solve(i,j-1,n,m,board,word,k+1); //left board[i][j] = ch; return op1||op2||op3||op4; } bool exist(vector& board, string word){ int n = board.size(); int m = board[0].size(); for(int i=0; i