Search Suggestions System - Leetcode 1268 - Python

[@NeetCode]

Discord: discord.gg/ddjKRXPqtk Correction: Time complexity is O(nlogn + n + m) where n is size of products, and m is length of searchWord.

[@masternobody1896]

Bug brain time

[@anon325]

It should be S*nlogn + n + m where s is avg string length.

[@aishwaryaranghar3385]

can you make a video one day for all the complexities.

[@tomyao7884]

Very nice correction

[@mirceanicolaescu9804]

it is actually a little worse than that because we have to account for copying over the strings into the result map at the end. so it would be something like S*nlogn + n + m * S

[@uditsharma5688]

Nice man , i used a binary search but two Pointer is more intuitive and easier to remember for me now. 👍

[@rockstars369]

For those who are wondering the purpose of 2nd pointer(right ptr.) as it isn't obvious in the video due to the example. In the example, it appears like we could get the solution for each typed character with constant amount of work i.e check the next 3 words from the current index of first pointer(left/top) and if they match the typed character add the word to the list and then append to the result List. The efficient way to verify the next 3 words from current index of first pointer(left ptr.) is just check the current char directly instead of reverifying all the previous chars of the next 3 words are also matching the prefix typed so far of the searchWord. Too much blabbering 🙃..... In short 2nd pointer is to limit the search space and guarantee that as long as the index of 1st pointer(left ptr) is less than or equal to 2nd pointer (right ptr) we are still in valid search space and avoid reverifying all the previous chars of the next 3 words from 1st pointer. Example : sorted search list = [mobile, monitor, mousepad, muumuu, tsunami, vault...] searchWord = mouse 1) char 'm' = [mobile, monitor, mouse] 2) char 'o' = [mobile, monitor, mouse] 3) char 'u' = [mouse] -> *current search char is 'u' with prefix searched so far "mo", without a second pointer we would have to reverify "mo" is also a prefix for words mousepad, muumuu, tsunami.*

[@lonen3rd]

You're right. The first idea that came to mind was Trie, but the implementation was not easy.

[@dianasvideos123]

Woah! This was my Amazon question last year! Thank you for this video, Neetcode! I’ve been meaning to re-attempt this! 😃

[@ObtecularPk]

Did you get it right?

[@dianasvideos123]

@@ObtecularPk No, I ran out of time 😅

[@ramkrushnamadole874]

Did u place in Amazon

[@ObtecularPk]

@@ramkrushnamadole874 what do you think? If she missed a question and ran outta time.

[@dianasvideos123]

@@ramkrushnamadole874 No, but I did get to try again 6 months later, and then I failed again 😅 But the moral of the story is- it wasn’t the end of the world 🙂 After that first failure, I was still able to interview with Meta (twice), Amazon again, and then Google as well last May 🙂 Each time I interviewed, I got A LOT better, but I’m still not quite there yet 🤷🏻‍♀️ I think if you want to interview with FAANG/MANGA, just do it 🙂 If anything, it’ll give you an idea of where you currently stand and what you need to work on 😄🤷🏻‍♀️

[@Mutual_Information]

Out of all the channels that try to help people transition into tech, this one has to be the most useful. Seriously these problem coding skills, as petty as they appear, as huge for getting an offer.

[@coderabbit118]

Thank you very much for these helpful videos. I did Blind75 and watched your solutions for those 75 questions! I must say, the solutions help me a lot for my tech round interviews!

[@zbynekjurica]

Wouldn't it be better to use binary search to move the pointers instead of just moving it by 1? Anyway, great explanation!

[@zr60]

binary search is more complex, because of the string slicing required in comparison.

[@joelpww]

Idk if it was corrected but lexicographically and alphabetically are different. The former is alphabetically order preceded by a length comparison

[@joelpww]

So this is asking for alphabetical and shortest results

[@nickheyer]

Hey @NeetCode, wouldn't it be faster to use a slice on the final append to answer instead of that for j in range loop? ie: answer.append(products[l:min(3, r - l + 1)+l])

[@ooow333]

result.append(products[l:r+1][:3]) also works

[@hugoibanez]

I really have no clue how are we supposed to come up with this sort of answers during an interview if we never saw the problem 😅

[@johnpaul4301]

yep same bro

[@shokhrukhabduahadov3985]

But question does not mention about products being sorted (or coming in order)

[@adityadhikle9473]

I think on your website you should list this problem under two pointers rather than binary search.

[@alanprado1652]

this is just to complex to get in my head :/. i always pause the video to try to understand it but i don't get when he adds a bunch of code in the same line, i feel frustrated😢

[@DavidDLee]

I'd use a TreeMap / std::map, which will do the l/r portion in logN time

[@tanishq2766]

Yeah i solved using the same technique

[@akhma102]

Thank you, Neet!

[@oscarheerkensthijssen5454]

How about res.append(products[l:min(l+3, r+1)]) instead of lines 15-18

[@raihanulalamhridoy4714]

Thank you. The explanation was really good. Better than leetcode solution page.

[@vineethsai1575]

The future generations are very lucky because by that time you might have completed videos for most of the leetcode problems!

[@sudhanshushekhar4222]

really amazing explanation....

[@shrimpo6416]

2 pointer solution is so neeeeeeeeeeeeet!!!

[@wintersol9921]

Your explenations are great.

[@NeetCode]

Thanks! 🙂

[@memeproductions4182]

Right pointer doesn't change complexity right?i could just iterate all words with left pointer and sfill find the first match, then just pick the first 3 matches from there

[@dynamic.6302]

Yes, as you iterate with your left pointer and check if it matches, you also need to check with left + 1 and left + 2 if it matches with the left pointer. And you need to ensure left + 1 and left + 2 are less than len(searchWord)

[@flamendless]

Question, would this algo scale for a database table (sorted always) with millions of data? hmmmmmmm

[@tempestofsouls5693]

Solved it using Trie + DFS. Should've realized that there was a much simpler solution using binary search or two pointer :/

[@shayanshayan8741]

Can I send a graph question and also a simple question that I didn't get to solve. Will you have look into that

[@PunithNayak-rj3fg]

Hey please mention the the time and space complexity for every question you solve

[@altusszawlowski4209]

He did at 7:47

[@EMdragonKnight]

Can you do this problem as a Trie?

[@austinhuang2454]

For the testcase of ["havana"] "havana", r will be 5, which occurs an error that list index out of range for products[r] and products[r][i]. How do you fix this?

[@austinhuang2454]

my bad, the right pointer should be len(products) - 1.

[@austinhuang2454]

which would fix the issue of my question

[@davidardo4466]

hello teacher, i have two question? math is important to software engineer? Second question? can i do better math? third/Sir, I'd like to work with Google in the future. Can I?

[@johnpaul4301]

go out and touch grass

[@neerajasanjay2375]

It gives a TLE now right?

[@bree9895]

here after a year! and after 2 jobs:)

[@trollbaron1329]

Hi Neetcode, love your succinct and clear explanation! Would you be willing to make videos on more advanced concepts like Segment Trees and String Hashing/KMP algorithm?

[@mdazharuddin4684]

I believe Trie will be more practical if the word list is mutable.

[@cyanimpostor6971]

It's more of a concept and application I believe

[@memeproductions4182]

How would you implement it with trie?i get you add all words character by character. But what when you search them up?you search until the prefix but then?you'll have to explore all the children subtrees and get the first 3 lexically minor

[@mdazharuddin4684]

@@memeproductions4182 maybe a dfs preorder traversal

[@dynamic.6302]

@@memeproductions4182 In your TrieNode class, have two attributes - children and suggestions. As you insert your product to the TrieNode, also add the product in the suggestions field. Suggestions can be an array and you can sort this array whenever you insert to it. Also, ensure that you pop out the elements whenever suggestions.size is greater than 3. Sorry if you didn't understand this. Will be happy to elaborate on this

[@mdazharuddin4684]

@@dynamic.6302 won't that take more time to keep updating the suggestion at every insert? I tried the dfs approach, took 2887ms while the two-pointer took only 115ms

[@aishwaryaranghar3385]

Thank You!

[@mk-19memelauncher65]

This doesnt seem scalable because you would need to sort every word first.

[@vivekshaw2095]

yesterday I took a test from aquasec this was my question with a bit of twist, insteaf of prefix I had suffix and instead of just one search word I had an array of multiple words

[@shantanukumar4081]

Masterpiece 👌👌👌

[@ohhellnooooo8233]

Hello, what's the app you use for doodling?

[@NeetCode]

Paint3d

[@ReAgent003]

@@NeetCode :D

[@janailtongoncalvesdesouza4160]

Very clever!

[@mageshyt2550]

const suggestedProducts = (products, searchWord) => { let ans = []; products.sort(); for (let i = 0; i < searchWord.length; i++) { const curr_search = searchWord.slice(0, i + 1); let temp = []; for (let j = 0; j < products.length; j++) { if (products[j].startsWith(curr_search)) { if (temp.length < 3) { temp.push(products[j]); } } } ans.push(temp); } return ans; };

[@__Y1a2s3h4__]

Leetcode 82 pls🙏

[@krateskim4169]

beautiful

[@pranavsharma7479]

easiest solution

[@dera_ng]

❤️

[@colin398]

5 seconds in: trie trie trie trie