Just landed a job at google thanks to you Neetcode! Weeks of falling asleep to your videos and studying my ass off really paid off and I really appreciate your work!
@@NeetCode Could you please do a video on matrix chain multiplication in dynamic programming? your explanations are clear and concise and better than other explanations
3:50 incorrect. insert or delete in middle of the linked list is not O(1). you need to find the node before insert or delete it, which is O(n) for the linked list
It's not "incorrect". Insertion itself is constant time, and there are cases where you already have the node you want to insert after. With an array, even if you know the index you want to insert at, it's O(n), so it's different. It is true that if you don't have a reference to the node you want to insert after, you'll have to search for it first, which is O(n).
Correction: Removing last node in a linked list: The time complexity of removing the last node in a linked list is O(n) and NOT O(1). To remove the last node of the linked list, we would have to traverse the linked list to the second last node (ie. node.next.next == null) and then remove the last node (ie. set node.next = null).
@@asaprogrammer_ correction on you. To remove the tail, you need to know the node before the tail (to point it to null). Unless you explicitly store it, you need to traverse the list to find it O(n)
Most implementations of a linked list track the size as you add/remove things so it is constant time to check the size. Depends on implementation though.
Insertion into the middle of a linked list is not constant. It’s O(N). You have to traverse the list to get to the node you want to insert. Same with deletion
Technically inserting and deleting from the middle is O(N) even for linked lists, however as articles don't consider indexing time when coming up with the Big O they say it is O(1).
You say inserting / removing from Linked List is 0(1), but for inserting at end, won't you need to traverse the whole list, go to the end and then insert? Wouldn't that make it O(n)? Space complexity would be O(1) since we aren't creating a new linked list.
Yeah that's true, while insert/delete anywhere in a linkedlist is O(1), the catch is you will most likely have to traverse it, so overall it will be O(n).
@@joakimolovsson7310 mahantesh is talking about a singly linked list where you have both the head and the tail pointer to have access to the first and the last element in O(1) time.
@@seongmoon6483 you make the tail pointer when you first create the linked list just like the head and maintain it every time you insert and remove. That’s O(1)
Pretty sure queues are usually implemented based on arrays. For double ended queues you can use a ring buffer. In most cases, the bad cache locality of linked lists makes them way slower so there are actually relatively few use cases where they really make sense.
In JavaScript where adding to the front of the array is O(n) you could benefit from using a linked list where adding to the front is constant time. Given huge problem instances, the locality is less of a problem than the time complexity (at least from my own testing I could be wrong).
@@theblackunderflow1842 Adding to the front of a resizable array is expensive in pretty much all languages. But for implementing queues, you just continue from the back when you want to insert before the start. That's what a ring buffer means. It's harder to judge performance in JS without trying it but likely linked lists will still be much worse. Usually, the only situation where linked lists are the best option performance-wise is when you need to do a lot of removing and adding to the middle of the list.
@@1vader Sorry, when you said queues I thought you were just referring to standard FIFO queues, with no maximum size or extra logic. I have not tested with double ended or circular queues. I have found that with basic queues, linked list implementation is much quicker than array. But, that wasn't what you were talking about haha that's my bad!
@@theblackunderflow1842 For a fifo Q you won't insert at the front though. Or at least you shouldn't. You just use pop() and push() which should be really fast. And you ideally should benchmark stuff like this with a real usage example. Micro-benchmarks which just push or pop a bunch in a row won't give you realistic data on this.
@@1vader How would you use push and pop for a Queue? I understand a stack, but I don't understand for a queue. Unless you were trying to implement a queue with two stacks?
I'm not sure if inserting to a hashmap is, by definition, O(1). It really depends on your hashing function. Your worst case to deal with hashing collisions will be by using a height balanced binary tree as collision structure, so this becomes O((logn)/k). If you never deal with collisions, then yeah O(1) is correct, but you'll need a really big starting array.
Removing from the end of a linked list is not O(1), as we need pointer to that node and for that we need to travese through the whole linked list to reach the 2nd last node.
Please answer... 1)According to you which is best website to practice coding... ? 2) Companies like Google in thier recruitment process make new ques or they ask from existing ques..?
When inserting/deleting from a linked list, don't you have to get the nodes 6 and 8 before inserting 7? But if you do, insert can't be O(1), since reading from a linked list is O(n)
Question: May be I am missing something ? But inserting or removing at the mid of linked list how it's O(1) unless we have a reference to the mid node, which in usual scenario we don't have that reference, in that case we have to loop to find the mid node and then insert or remove in this case it won't be constant.
I don't understand the logic for a linked list's time complexity. If it takes O(n) to access an element, how can it take O(1) to insert? Don't we need to access the element i-1 in order to change it's pointer to the new item?
It's take O(n) to access a specific element because traverse it which means you run from the first node to the last one so in the worse case you will have to run though all the elements which is o(length) = o(n). If you want to insert element it will be o(1) only in case you have the pointer to it so you can make a new node and change the pointers from the prev to the new one and the new one into the next. BUT in case you need to traverse first (to find the spot which you want to add the new element) will take you o(n) for the traverse and o(1) to insert it to the specific spot which will adds up to o(n) overall.
Regarding Linked list how it's possible to insert or remove in middle of the linked list in O(1)? How you will get the node of middle in constant time without storing the index of the nodes of the linked list?
@NeetCode , One que, How time complexity of linked list for insert and delete will be O(1), first we need to traverse till that node right ?, which in worst case O(n). so O(n) + O(1) would be O(n) right ?
Question: Certain languages have built-in min/max heap and other DS libraries that you can call upon if you recognize them as a useful tool for solving a problem. However, other languages don't (and unluckily, my preferred language doesn't) During interviews, is it kosher to at least have the class implementation and methods saved somewhere you can copy paste in, since the interviewer probably cares more that you recognized when and how to use them? Mostly because I can explain and write out a Trie's basic methods in a few minutes, but to implement a heap from scratch will take way too much time.
why are hash maps said to have O(1) key search/access/insert time, when conflicts exist? Is there an implementation that works in O(1) in presence of conflicts? I trust STL to be well implemented, and STL guarantees O(lg) for sorted and O(N) for unordered maps/sets.
@NeetCode, could you please make a video or attach some links to help understand the complexity analysis of Backtracking problems ? For me, calculating the TC of backtracking problems is more tough than actually coding the solution.
Why hen we insert in the middle of linked list - it is not considered as O(n)? We need to traverse LL to the position where we want to insert an element
As far as I know, inserting an element at any position to a linked list is O(N) because you have to traverse and update your pointer untill that element. In the video it says O(1). How is this possible?
3:58 i've never understood why inserting & deleting the middle of the linked list is O(1). how does it suddenly find the pointer to the middle element? shouldn't it be O(n) because you still need to iterate from the first element to the n-th element if you wanna insert or remove it?
Technically it's O(1) when you insert or remove, but yes, practically it's O(n) because you have to iterate to the position. But with arrays, it's O(n) regardless This distinction can be important sometimes, like in the LRU cache problem
DUDE... its a request plz plz plz either get a better microphone or speak a bit louder... haha... im literally playing it on Loudspeakers yet ur vids sound like a squeak...
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Hes at Google but he doesn’t stop. A true champion!
The hero we don't deserve.
Coz that's what heroes do
He’s at Google yet teaches linked list concept wrong
Just landed a job at google thanks to you Neetcode! Weeks of falling asleep to your videos and studying my ass off really paid off and I really appreciate your work!
Nice, congrats!!!
@@NeetCode Could you please do a video on matrix chain multiplication in dynamic programming? your explanations are clear and concise and better than other explanations
@@darkshadow_323 u done strassens matrix multiplication? its n^2.7 tc
What was your preferred choice of language for interview?
@@NeetCode
A must watch for anyone grinding for tech interviews
3:50
incorrect. insert or delete in middle of the linked list is not O(1).
you need to find the node before insert or delete it, which is O(n) for the linked list
It's not "incorrect". Insertion itself is constant time, and there are cases where you already have the node you want to insert after. With an array, even if you know the index you want to insert at, it's O(n), so it's different. It is true that if you don't have a reference to the node you want to insert after, you'll have to search for it first, which is O(n).
Hey man, I just signed an offer from Google today and I feel like I couldn't do this without you! Many many thanks for your videos!
That's so great to hear, congratulations!!! 🎉
How did you study?
@@TheStrafendestroy blind 75 grind for 3ish months
@@nightmarauder2909 thank you!
Correction:
Removing last node in a linked list:
The time complexity of removing the last node in a linked list is O(n) and NOT O(1). To remove the last node of the linked list, we would have to traverse the linked list to the second last node (ie. node.next.next == null) and then remove the last node (ie. set node.next = null).
@@asaprogrammer_ correction on you. To remove the tail, you need to know the node before the tail (to point it to null). Unless you explicitly store it, you need to traverse the list to find it O(n)
@@ianakotey yep, you're right. I forgot to mention that you need to store it to get O(1) Thanks!
Removing elements from linked lists by “index” should also take O(n).
I think u need to iterate over the linked list to know the middle(as in the size) then iterate till you find the value in the linked list
Most implementations of a linked list track the size as you add/remove things so it is constant time to check the size. Depends on implementation though.
@@ezrahuffman still O(n) to get to the middle even when you know lists length. Unless you maintain relevant pointer to the middle somehow
Thank you! The summer grind of algorithms starts now!
Yeah
Same, and my internship as a full stack dev rip
Same
We all are going to make it, trust
Yessir!!
I actually relearn all of data structure in this man. Keep it up
Insertion into the middle of a linked list is not constant. It’s O(N). You have to traverse the list to get to the node you want to insert. Same with deletion
depends on if u have a tail pointer or not
Technically inserting and deleting from the middle is O(N) even for linked lists, however as articles don't consider indexing time when coming up with the Big O they say it is O(1).
You say inserting / removing from Linked List is 0(1), but for inserting at end, won't you need to traverse the whole list, go to the end and then insert? Wouldn't that make it O(n)? Space complexity would be O(1) since we aren't creating a new linked list.
Yeah that's true, while insert/delete anywhere in a linkedlist is O(1), the catch is you will most likely have to traverse it, so overall it will be O(n).
Most implementations use a tail pointer to point to last element which gets updated when inserting at end, making this O(1) for inserting at end.
@@mahanteshambali most questions I've seen are about singly linked lists
@@joakimolovsson7310 mahantesh is talking about a singly linked list where you have both the head and the tail pointer to have access to the first and the last element in O(1) time.
@@frank3110 ah I see! My bad :)
Dude best thing about you is you are a good teacher and world have very limited good teachers.
You need to traverse the linked list to insert in the middle so it is actually O(n)
My thoughts exactly. Also, removing End would be O(n) IF you did not have a previous pointer.
@@seongmoon6483 you can have a tail pointer even with a singly linked list to remove the last element in constant time
@@tofahub You need to traverse to the 2nd last node to set that as the new tail and set its next to null
It seems like he just didn't include the traversal.
@@seongmoon6483 you make the tail pointer when you first create the linked list just like the head and maintain it every time you insert and remove. That’s O(1)
Pretty sure queues are usually implemented based on arrays. For double ended queues you can use a ring buffer. In most cases, the bad cache locality of linked lists makes them way slower so there are actually relatively few use cases where they really make sense.
In JavaScript where adding to the front of the array is O(n) you could benefit from using a linked list where adding to the front is constant time. Given huge problem instances, the locality is less of a problem than the time complexity (at least from my own testing I could be wrong).
@@theblackunderflow1842 Adding to the front of a resizable array is expensive in pretty much all languages. But for implementing queues, you just continue from the back when you want to insert before the start. That's what a ring buffer means. It's harder to judge performance in JS without trying it but likely linked lists will still be much worse. Usually, the only situation where linked lists are the best option performance-wise is when you need to do a lot of removing and adding to the middle of the list.
@@1vader Sorry, when you said queues I thought you were just referring to standard FIFO queues, with no maximum size or extra logic. I have not tested with double ended or circular queues. I have found that with basic queues, linked list implementation is much quicker than array. But, that wasn't what you were talking about haha that's my bad!
@@theblackunderflow1842 For a fifo Q you won't insert at the front though. Or at least you shouldn't. You just use pop() and push() which should be really fast. And you ideally should benchmark stuff like this with a real usage example. Micro-benchmarks which just push or pop a bunch in a row won't give you realistic data on this.
@@1vader How would you use push and pop for a Queue? I understand a stack, but I don't understand for a queue. Unless you were trying to implement a queue with two stacks?
Absolute next level channel and website. Notifications on, you are doing gods work sir
I'm not sure if inserting to a hashmap is, by definition, O(1). It really depends on your hashing function. Your worst case to deal with hashing collisions will be by using a height balanced binary tree as collision structure, so this becomes O((logn)/k). If you never deal with collisions, then yeah O(1) is correct, but you'll need a really big starting array.
Yes, I believe that's called amortised O(1)?
I know you have already done so much could you do a series on how to determine time and space complexity
He doesnt know what he is talking about in this topic, you better look elsewhere.
Removing from the end of a linked list is not O(1), as we need pointer to that node and for that we need to travese through the whole linked list to reach the 2nd last node.
actually, most hashmaps are built on linked lists utilizing chaining.
Thanks you, I wish I had a job I would’ve send you more!
Hi, I have two questions 1) how about disjoint set, is it important? 2) does an AI Engineer/ AI researcher need a lot of leetcode?
Please answer...
1)According to you which is best website to practice coding... ?
2) Companies like Google in thier recruitment process make new ques or they ask from existing ques..?
After joining Google, how do you manage personal time with your job?
When inserting/deleting from a linked list, don't you have to get the nodes 6 and 8 before inserting 7? But if you do, insert can't be O(1), since reading from a linked list is O(n)
Thank you so much. Can you please make same type of video on top Algorithms.
Thanks in advance
Nice! Very helpful. Until seeing this I thought linked lists were just for making Leetcode questions. Thank you for making this
There are concrete like arrays and linked lists and maybe even trees and abstract data structures like graphs and hashtables..
Super helpful, have tech interview in month, super nervous lol this was very helpful thank you
Question: May be I am missing something ? But inserting or removing at the mid of linked list how it's O(1) unless we have a reference to the mid node, which in usual scenario we don't have that reference, in that case we have to loop to find the mid node and then insert or remove in this case it won't be constant.
Hey there thanks so much for your content
I really need to know the tool u use to draw on the screenshot while illustrating the problems
Nice 😊 I was searching a similar content ✌🏻
Can you do a video on how to prepare for the Googlyness interview?
Neetcode you're the BEST!!!
i would add to hashmap that finding depends on its implementation
Neet, what is a good use case for each data structure?
I don't understand the logic for a linked list's time complexity. If it takes O(n) to access an element, how can it take O(1) to insert? Don't we need to access the element i-1 in order to change it's pointer to the new item?
It's take O(n) to access a specific element because traverse it which means you run from the first node to the last one so in the worse case you will have to run though all the elements which is o(length) = o(n).
If you want to insert element it will be o(1) only in case you have the pointer to it so you can make a new node and change the pointers from the prev to the new one and the new one into the next.
BUT in case you need to traverse first (to find the spot which you want to add the new element) will take you o(n) for the traverse and o(1) to insert it to the specific spot which will adds up to o(n) overall.
Regarding Linked list how it's possible to insert or remove in middle of the linked list in O(1)? How you will get the node of middle in constant time without storing the index of the nodes of the linked list?
Shouldn’t insertion in between the list about O(n/2) for worst case? Since you have to traverse the list and do the insertion?
@NeetCode , One que, How time complexity of linked list for insert and delete will be O(1), first we need to traverse till that node right ?, which in worst case O(n). so O(n) + O(1) would be O(n) right ?
Just in time sir!!!! Thank you so much!
I’ll be honest, I have YET to have a coding interview where they wanted me to do a problem using a linked list.
Question:
Certain languages have built-in min/max heap and other DS libraries that you can call upon if you recognize them as a useful tool for solving a problem. However, other languages don't (and unluckily, my preferred language doesn't)
During interviews, is it kosher to at least have the class implementation and methods saved somewhere you can copy paste in, since the interviewer probably cares more that you recognized when and how to use them? Mostly because I can explain and write out a Trie's basic methods in a few minutes, but to implement a heap from scratch will take way too much time.
Please do a video on Leetcode 907. Sum of subarray minimums.
Hey neet can you please release a ds and algos course for python since there aren't any good ones out there
How do you draw during a google docs whiteboard? Do you have a stylus or do you use a mouse?
why are hash maps said to have O(1) key search/access/insert time, when conflicts exist? Is there an implementation that works in O(1) in presence of conflicts?
I trust STL to be well implemented, and STL guarantees O(lg) for sorted and O(N) for unordered maps/sets.
Could you please make a video on leet code problem "1192. Critical Connections in a Network"
hey, what is the material that you use for creating these videos? that tools are you using?
@NeetCode, could you please make a video or attach some links to help understand the complexity analysis of Backtracking problems ? For me, calculating the TC of backtracking problems is more tough than actually coding the solution.
What is a backtracking problem?
I love the linked list😍😁
Is this needed for ALL interview like entry level or junior positions or just top tech FAANG/MAANG like companies??
Please make a video on time complexity Big O using python
Fantastic video!
Removing a node at the end is not constant. Not in a single linked list
Hi neetcode can you suggest best resources to study linked list?
What software do you use to write on the video ? you know whiteboard thing that you do in videos
Thanks for this 😊
Why hen we insert in the middle of linked list - it is not considered as O(n)? We need to traverse LL to the position where we want to insert an element
Hey!
Can you recommend and system design site/source?
fantastic one
Thanks!
As far as I know, inserting an element at any position to a linked list is O(N) because you have to traverse and update your pointer untill that element. In the video it says O(1). How is this possible?
I think he means inserting at the front or back but other wise it is O(n)
wouldn't for linked list insert and remove middle still be O(n) because you need to spend time navigating to that element?
I had the same doubt
3:58 i've never understood why inserting & deleting the middle of the linked list is O(1).
how does it suddenly find the pointer to the middle element?
shouldn't it be O(n) because you still need to iterate from the first element to the n-th element if you wanna insert or remove it?
Technically it's O(1) when you insert or remove, but yes, practically it's O(n) because you have to iterate to the position. But with arrays, it's O(n) regardless
This distinction can be important sometimes, like in the LRU cache problem
I have a request for a leetcode problem Can you solve 1079. Letter Tile Possibilities
Is trhere any situation, where an array is faster or more efficient than a hashmap?
what app do you use for whiteboard?
Hey NeetCode, Can you recommend a free interactive source to learn the Big O Theory?
Check inside code free course on Big O notation
@@yogeshmotiyani3535 Can you kindly drop a link for that please
Search Kunal Kushwaha on youtube. You will find his video on Time Complexity.
Do you have a prepfully account? Can we contact you for a practice swe intern interview?
I thought arrays were immutable in size?
i try to maintain consistency but getting failing. what should i focus on ds or develpment.
Dsa practice helps when you start development . Not directly but logic starts clicking faster. So DSA first.
I am doing both. It is a good way imo.
do both, sometimes yeah I also too get too indulged on one side, but after some times I'm able to balance between them.
loved it
Please, ease up on the embedded ads. There are three of them here (three!). I pay for TH-cam Premium.
By the time you read this comment, I'll be in FAANG.
Where are you working now?
Cool.
DUDE... its a request plz plz plz either get a better microphone or speak a bit louder... haha... im literally playing it on Loudspeakers yet ur vids sound like a squeak...
first comment left by me
Stack is used more than linkedlist
literally my uni course in 13min.
day 10 of asking neet to make a video on how to communicate during coding interviews 🥲