Search Suggestions System - Leetcode 1268 - Python

0:00 - Read the problem
0:55 - Drawing Explanation
8:25 - Coding Explanation

leetcode 1268

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[NeetCode]

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

[dianasvideos]

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

[uditsharma]

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

[lonenrd]

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

[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.

[coderabbit]

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!

[rockstars]

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<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.*

[vineethsai]

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

[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 😅

[zbynekjurica]

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

Anyway, great explanation!

[RaihanulAlamHridoyOfficial]

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

[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])

[joelpww]

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

[oscarheerkensthijssen]

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

[DavidDLee]

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

[alanprado]

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😢

[austinhuang]

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?

[adityadhikle]

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

[flamendless]

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

[memeproductions]

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