incredible hard to be the first question!!!! I will try to study this a lot more, i will do a brute force in my mind in order to get what you did here!
But you are going to be copying memory here right? every single time you need to add a new value to the array, the array will be recreated in memory? Incase of the array being a lot larger than 3-6 int's the array will be changed multiple times which causes other issues right? is this really the greatest solution?
We are not modifying the input array in any way. At each iteration, if the two numbers haven't been found, we only add a key-value pair to the "seen" dictionary, and dictionary insertions run in (amortized) O(1) time.
Hello, I have one question regards to linear time solution which is mentioned here, I understand when we are traversing through the list only once.. While we are checking if the element i.e Target- list elem in dictionary we are doing o(1) n times which again corresponds to O(N) so O(n) * O(n).. sorry i m wrong, request you to please correct me.
The misunderstanding here is that hash table (dictionary) lookup is not "O(1) n times" - it is just O(1). When checking if an element exists in a hash table, we do not iterate through all the keys. Instead, the element is converted into an "index" via a hash function, which allows you to jump straight to where the element should be in the hash table, similar to how array lookup is O(1) if you have the index.
You may be mistaken - sets and hash tables are inherently unordered so there is no concept of an index. However, with a hash table, you can access elements with a key instead, as we do in this problem.
@@AlgoEngine Yeah, I'm pretty new to this Python. I see at line 6 (3:54), you can use seen[diff], like array indices. Do you need to tell Python if 'seen' is a HashTable or Set beforehand?
@@st-lucia Ah, so Python knows that "seen" is a Dictionary (hash table) because we initialized it using curly braces like this: seen = {}. You could also do it like this: seen = dict(). Now, to access elements inside a hash table, we use a key (instead of an index for an array). seen[diff] returns the value corresponding to the key of diff, but remember, hash table keys can be anything and have no order (unlike array indexes, which must be ordered integers).
Start with learning/reviewing all the basic algorithms and data structures and understanding their time and space complexities. After you have the basics down, the best way to learn is to practice! I'd recommend setting aside 20-30 min for each problem (depends on how much time you have), and if you don't get it by then, just look at the solution but make sure you understand it. Then after a few days, revisit the problem and try to solve it without looking at the solution.
I address this point at 4:59. Those two methods are not the same because "diff in seen" is O(1) but "diff in seen.keys()" is O(n). Hash table collisions could degrade the performance, but if the hash table is well implemented, this should rarely happen so the amortized complexity is still O(1). See the discussion here for more information: stackoverflow.com/a/17539425
Only if the duplicates create multiple solutions, but this problem assumes that there is exactly one solution. If multiple solutions were allowed, it would depend on whether you need to return all solutions or just one of the solutions. If you only need to return one, nothing changes, but if you must return all, then yes, you’d have to take a different approach.
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/mqdefault.jpg)
Thank you for sharing your knowledge and expertise with the world!
Extremely clear and well presented video. Here's a comment for the RUclips algorithm.
You save me man, thank you. Now a can learn python and english with that subtitles.
Omg I needed this. YOU'RE AWESOME
Keep up bro! Your vids are extremly useful !
Learned a lot from the explanation.
Great tutorial!
Thank you, excellent explanation!
You did an incredible job. Great explanation and pace!
Ты великолепен! Куда отправить деньги чтобы поддержать твое творчество?🤗
you made it a lot easier. TYTYTY
Great video!
incredible hard to be the first question!!!! I will try to study this a lot more, i will do a brute force in my mind in order to get what you did here!
Keep going 🔥🎉
oh my god my head hurts. Thank youy
Waiting for upcoming videos
Great explanation. I'm trying to imagine what that syntax would look like in Java.
Best explanation out there!
Your the best! Great video.
Thanks bro for sharing your knowledge and for explaining clearly
Great explanation and visualization, thank you
Thank you for sharing your knowledge. You helped me a lot!
very simple explanation thank you
Thank you
Brute. This guy knows his Brute Forces
😂
ajig aing can ngarti, masih smp, rek ka smk jurusan rpl, bakal diajar anu kieu moal nya, siap siap heula we ah
I see, so this is what I overlooked...
But you are going to be copying memory here right? every single time you need to add a new value to the array, the array will be recreated in memory? Incase of the array being a lot larger than 3-6 int's the array will be changed multiple times which causes other issues right? is this really the greatest solution?
We are not modifying the input array in any way. At each iteration, if the two numbers haven't been found, we only add a key-value pair to the "seen" dictionary, and dictionary insertions run in (amortized) O(1) time.
Hello, I have one question regards to linear time solution which is mentioned here, I understand when we are traversing through the list only once.. While we are checking if the element i.e Target- list elem in dictionary we are doing o(1) n times which again corresponds to O(N) so O(n) * O(n).. sorry i m wrong, request you to please correct me.
The misunderstanding here is that hash table (dictionary) lookup is not "O(1) n times" - it is just O(1). When checking if an element exists in a hash table, we do not iterate through all the keys. Instead, the element is converted into an "index" via a hash function, which allows you to jump straight to where the element should be in the hash table, similar to how array lookup is O(1) if you have the index.
@@AlgoEngine Thank you ... Nice one !
I read somewhere that Sets can access index like Arrays/Lists.
How do you overcome this? Tysm!
You may be mistaken - sets and hash tables are inherently unordered so there is no concept of an index. However, with a hash table, you can access elements with a key instead, as we do in this problem.
@@AlgoEngine Yeah, I'm pretty new to this Python.
I see at line 6 (3:54), you can use seen[diff], like array indices.
Do you need to tell Python if 'seen' is a HashTable or Set beforehand?
@@st-lucia Ah, so Python knows that "seen" is a Dictionary (hash table) because we initialized it using curly braces like this: seen = {}. You could also do it like this: seen = dict().
Now, to access elements inside a hash table, we use a key (instead of an index for an array). seen[diff] returns the value corresponding to the key of diff, but remember, hash table keys can be anything and have no order (unlike array indexes, which must be ordered integers).
@@AlgoEngineok
Kind of get it now.
I will try to run the code, thank you again for the help!
which video editing software are you using to make this video?
I mainly use HTML, CSS, and JavaScript to make these, and occasionally PowerPoint.
@@AlgoEngine 😍😍😍 thanks so much
What software you use for animations ?
I mostly use HTML, CSS, and JavaScript to create these. Occasionally, PowerPoint for the shorter ones.
My brain just died i have no knowledge of math since i didn't listen when i was in highschool, any tips to begin?
Start with learning/reviewing all the basic algorithms and data structures and understanding their time and space complexities. After you have the basics down, the best way to learn is to practice! I'd recommend setting aside 20-30 min for each problem (depends on how much time you have), and if you don't get it by then, just look at the solution but make sure you understand it. Then after a few days, revisit the problem and try to solve it without looking at the solution.
Try to always keep the original LC # in your title.
Your optimized solution not O(n) in worst case it still O(n^2), becouse "diff in seed" = diff in seen.keys() is O(n) lookup.
I address this point at 4:59. Those two methods are not the same because "diff in seen" is O(1) but "diff in seen.keys()" is O(n). Hash table collisions could degrade the performance, but if the hash table is well implemented, this should rarely happen so the amortized complexity is still O(1). See the discussion here for more information: stackoverflow.com/a/17539425
aren't you fucked if the array has dupes?
Only if the duplicates create multiple solutions, but this problem assumes that there is exactly one solution. If multiple solutions were allowed, it would depend on whether you need to return all solutions or just one of the solutions. If you only need to return one, nothing changes, but if you must return all, then yes, you’d have to take a different approach.
Such a clear and well-explained video, thank you! 🩵