Delete Nodes From Linked List Present in Array - Leetcode 3217 - Python

Summary

In this coding tutorial, the focus is on solving the problem of deleting nodes from a linked list that are present in an array. The video demonstrates the use of a hash set for efficient lookup, which reduces the time complexity to O(n+m). A dummy node is introduced to simplify the removal process, and a two-pointer approach is explained to iterate through the list and remove the nodes. The tutorial also covers a one-pointer alternative for deletion. The video concludes with a live coding session, showcasing the efficiency of the solution.

Takeaways

• 📝 The video tutorial focuses on solving the problem of deleting nodes from a linked list based on values present in an array.
• 🔍 The presenter suggests using a hash set for constant time lookups to determine if a node's value exists in the given array.
• 🔑 The idea is to iterate through each node of the linked list and remove it if its value is found in the hash set.
• 🔁 The tutorial introduces the concept of a 'dummy node' to simplify the process of node deletion in a linked list.
• 💡 The presenter explains that with a dummy node, you can handle edge cases like deleting the head of the list more easily.
• 🔭 The video demonstrates a two-pointer approach to traverse and modify the linked list, keeping track of the current and previous nodes.
• ⏱️ The time complexity of the algorithm is discussed as O(n + m), where n is the length of the linked list and m is the size of the array.
• 💾 Space complexity is noted as O(n) due to the additional hash set data structure used for lookups.
• 👨‍💻 The presenter provides a step-by-step coding example in Python, emphasizing the importance of not skipping nodes during deletion.
• 🔄 An alternative single-pointer approach is also discussed, showing adaptability in solving the problem with different methods.
• 📢 The tutorial ends with a call to action for viewers to subscribe for more content on data structures, system design, and related topics.

Q & A

What problem is the video tutorial addressing?

The video tutorial is addressing the problem of deleting nodes from a linked list that are present in a given array.

What is the expected outcome if all nodes in the linked list are removed?

If all nodes in the linked list are removed, the head of the remaining list could be null, indicating an empty list.

Why does the tutorial suggest using a hash set for lookup?

The tutorial suggests using a hash set for lookup because it provides constant time complexity for lookups, making the process more efficient compared to linear scans.

What is the role of a dummy node in linked list problems?

A dummy node simplifies the process of modifying a linked list, especially when dealing with edge cases such as removing the head of the list or nodes from the beginning.

How does the tutorial propose to remove a node from the linked list?

The tutorial proposes using a two-pointer approach where one pointer keeps track of the previous node and the other of the current node, adjusting the pointers to effectively remove the current node if its value is in the hash set.

What is the time complexity of the algorithm described in the tutorial?

The time complexity of the algorithm is O(n + m), where n is the number of nodes in the linked list and m is the size of the array.

What is the space complexity of the algorithm?

The space complexity of the algorithm is O(n), which is due to the additional space used by the hash set to store the values from the array.

Why does the tutorial mention not shifting the previous pointer when a node is deleted?

Shifting the previous pointer when a node is deleted could lead to skipping a node in the list, which is incorrect behavior for the problem at hand.

What alternative method does the tutorial suggest for solving the problem?

The tutorial suggests an alternative method using only one pointer, which simplifies the code by always moving the pointer one step ahead.

How does the tutorial ensure that the original order of the nodes is maintained after deletions?

The tutorial ensures that the original order is maintained by only adjusting the pointers to skip over the nodes that are to be deleted, without changing the order of the remaining nodes.

What additional resources does the tutorial mention for further learning?

The tutorial mentions a free newsletter and upcoming system design videos as additional resources for further learning on data structures, system design, and more.

Outlines

00:00

👨‍💻 Solving the Delete Nodes from Linked List Problem

This paragraph introduces a coding challenge to delete nodes from a linked list based on values present in an array. The speaker proposes using a hash set for efficient lookups to determine if a node's value should be removed. The approach involves iterating through the linked list and removing nodes whose values exist in the hash set. A dummy node is suggested to simplify the removal process, especially for nodes at the beginning of the list. The speaker explains the use of two pointers, one to keep track of the previous node and another for the current node, to efficiently delete nodes without skipping any. The time complexity is discussed as O(n+m), where n is the length of the linked list and m is the size of the array, and the space complexity is O(n) due to the hash set.

05:01

🔍 Optimizing with a Single Pointer Technique

The second paragraph explores an alternative solution to the linked list node deletion problem using only a single pointer. The speaker refactors the code to eliminate the need for a 'current' pointer, relying solely on a 'previous' pointer to manage node deletions. The approach involves checking if the next node in line should be deleted and, if so, adjusting the 'previous' pointer to skip over it. If not, the 'previous' pointer is simply moved forward. The speaker runs the optimized code to demonstrate its effectiveness and mentions that, while this single-pointer technique might not be more efficient, it is a valid alternative. The paragraph concludes with a teaser for upcoming content, including a free newsletter and system design videos.

Keywords

💡Linked List

A linked list is a linear data structure where each element is a separate object, called a node, which contains a reference to the next node in the sequence. In the context of the video, the linked list is the primary data structure being manipulated. The video aims to solve the problem of deleting nodes from a linked list based on values present in an array, which involves traversing the linked list and removing nodes that match the values in the array.

💡Array

An array is a data structure consisting of a collection of elements, each identified by one or more indices or keys. In the video, an array of numbers is given alongside the linked list. The task is to remove nodes from the linked list if their values exist within this array, demonstrating the use of arrays for storing and comparing data.

💡Hash Set

A hash set is a data structure that allows for quick lookups, insertions, and deletions of elements based on their hash values. In the video, a hash set is used to store the values from the array to enable constant time lookups when determining if a node in the linked list should be removed. This is a key optimization to improve the efficiency of the algorithm.

💡Dummy Node

A dummy node is a placeholder node used in algorithms involving linked lists to simplify operations such as insertions and deletions, especially at the head of the list. The video script mentions using a dummy node to facilitate the removal of nodes from the linked list without having to handle special cases for the head of the list separately.

💡Two-pointer Technique

The two-pointer technique is an algorithmic approach where two pointers are used to traverse a data structure, often used to check for certain conditions or to manipulate the structure. In the video, this technique is used to keep track of the previous and current nodes in the linked list while iterating through it to decide which nodes to delete.

💡Time Complexity

Time complexity is a measure of the amount of time an algorithm takes to run as a function of the length of the input. The video discusses the time complexity of the algorithm for deleting nodes from a linked list, highlighting the importance of understanding how different operations contribute to the overall efficiency of the solution.

💡Space Complexity

Space complexity is a measure of the amount of memory an algorithm uses in relation to the size of the input. The video mentions the space complexity in the context of using a hash set, which stores the values from the array, and discusses how it affects the overall resource usage of the algorithm.

💡Node Removal

Node removal refers to the process of deleting a node from a linked list. In the video, this is the primary operation being performed, and it is discussed in detail, including how to handle the removal of nodes from different positions in the list, such as the head or middle of the list.

💡Constant Time

Constant time, often denoted as O(1), is a term used in computer science to describe an operation that takes the same amount of time to complete regardless of the size of the input. The video emphasizes the use of a hash set to achieve constant time lookups for values when deciding whether to remove a node from the linked list.

💡Algorithm

An algorithm is a step-by-step procedure for calculations, data processing, or automatic reasoning. The video outlines an algorithm for deleting nodes from a linked list based on values in an array, which includes creating a hash set, iterating through the linked list, and applying the two-pointer technique to remove nodes.

💡Linear Scan

A linear scan is a method of searching through a data structure by checking each element in sequence until the desired element is found. The video mentions linear scan as one of the initial approaches considered for looking up values in the array before opting for a hash set for more efficient constant time lookups.

Highlights

Introduction to solving the problem of deleting nodes from a linked list based on values in an array.

Explanation of the need to remove nodes from a linked list if their values exist in a given array.

Discussion on the potential outcomes of the linked list after node deletion, including it being empty or null.

Proposing the use of a hash set for efficient lookup to determine if a node's value exists in the array.

Algorithm outline for iterating through the linked list and removing nodes based on the hash set lookup.

Introducing the concept of a dummy node to simplify linked list modifications.

Demonstration of how to handle edge cases when removing nodes from the beginning of the linked list.

Trick for using two pointers to keep track of the previous and current nodes for deletion.

Explanation of why not to shift the previous pointer when a node is deleted to avoid skipping nodes.

Code implementation of the algorithm using a hash set and two-pointer technique.

Time complexity analysis of the algorithm, considering the size of the linked list and array.

Space complexity discussion, noting the use of a hash set and its impact on space usage.

Alternative solution using only one pointer for node deletion, simplifying the code.

Final code review and demonstration of the solution's efficiency.

Announcement of upcoming educational resources, including a free newsletter and system design videos.

Transcripts

hey everyone welcome back and let's

write some more neat code today so today

I'll solve the problem delete nodes from

linked list present in an array so I'll

keep this one nice and short the idea is

we're given a linked list that might

look like this we're also given an array

of numbers if any of these nodes has a

value that exists within that array we

want to remove that node from the linked

list and so in this case we would remove

all three of these and then return the

remaining linked list it could could be

empty I mean it could technically be

null it could be non-empty and if it's

non-empty of course we want to return

the original notes we want to return the

head of the remaining list how do we go

about solving this problem well the

first thing that you need to do is how

do we do the lookup how do we know if

this value exists in there we can do a

linear scan we can go through that

entire thing either by looping over it

or using a built-in function but since

it's an array it's going to be linear

time lookups though are quicker when

hash data structures whether it's a hash

map or in this case a hash set is going

to be sufficient so that's exactly what

we're going to do the lookup in that

case will go from oven to constant time

so the algorithm is going to be this go

through each node if the value exists in

the hash set we will convert this into a

hash set then remove the node okay so

now you might be wondering how do we go

about removing a node well the first

thing I want to tell you is that there

is a trick with link list problems you

almost always want to have a dummy node

when you're modifying a linked list it

makes the code just a little bit easier

let me show you what I mean like this

example here if we were updating this

link list we'd say that okay well right

now we have a pointer this is the head

of the link list and we are now trying

to delete it okay so since this is the

head we should probably change the head

pointer to now be at the next node but

if we were removing a node from the

middle suppose this one down here like

this is our head right now we're not

removing the head we're removing the

node after the head so in that case we

just want to take this pointer and then

shift it over there so we can remove the

difference between both of these by

doing something called a dummy node The

Edge case comes from the fact that we

could remove from the beginning of the

list so let's just create a random node

doesn't really matter what the value is

I'll say it's zero and let's set the

next pointer to the head of the existing

link list now we're going to do the

exact same thing as before this is a one

so let's remove it how do we do that

well one possible way is to use two

pointers keep track of the previous node

and keep track of the current node and

if the current node is something we want

to delete then take the previous next

pointer and set it to current. next

that's pretty much going to remove it

and then in this particular case the

previous pointer should stay here it

should not be shifted our current

pointer should only be shifted here

because if we shift both of the pointers

if we put the previous pointer over here

and the current pointer over here we're

g to consider removing this one we're

going to check okay is this a value we

want to remove and then we'll end up

removing it but we ended up skipping

this guy so that's why you don't want to

shift the previous poter if you deleted

the node okay but what if we don't

delete the node suppose we weren't

deleting this one well then we would

shift both of the pointers then we would

shift previous by one and we would shift

current by one and then you know do the

same thing here so that's more or less

how you go about solving the problem I

think we're actually ready to code this

up very quickly let's go over the time

and space we're given two inputs the

size of them is not necessarily going to

be the same let's say this is n let's

say this is M so overall the time

complexity we're going to convert this

into a hashset and we're going to

iterate over the entire link list that's

going to be n plus m space we are using

a data structure the hash set remember

so that's going to be Big O of n now

let's code it up so the first thing I'm

going to do is just take nums and

convert it into a hash set I'm able to

do this in Python because there's no

like static typing you might not be able

to do that in your own language you

might have to create a new variable name

um but now let's do the Demi node let's

create a random node and let's give it a

value of zero it doesn't really matter

what value we give it let's set the next

pointer though to the head of the given

linked list here and now let's basically

do that two-pointer thing I was talking

about having the previous pointer set to

uh the Demi node initially and then the

current pointer set to the head or we

could say dummy. next but it doesn't

really matter they're both the same and

now we say while current because current

is the node that we're considering to

delete and so we're going to check if

the current. Val is in the nums hash set

then we want to delete it and that's

very easy to do we just say previous do

next is equal to current. next and

remember in this case we don't shift the

previous pointer we don't want to do

that we don't want to skip a node we

only shift the current pointer so say

current is now going to be current. next

now the alternative is where we don't

delete the node in that case it's pretty

simple we just shift both of the pointer

so previous will be previous nextt

current will be current. nextt you might

notice that there is a duplicate line in

both of these conditions it doesn't

really matter in a real interview I

personally wouldn't care that much but

it does make the code a little bit

better so I'm going to go ahead and move

this line out of the if statement and

then delete this one lastly at the end

we are going to return

dummy. nextt if we ended up deleting

every single Noe in the linked list what

would dummy. nextext point to it would

probably point to null if we didn't

delete every single node it's going to

point to the new head of the link list

cuz even though we're deleting nodes

we're never changing the order of them

so this is the whole solution let's run

it as you can see it works it's pretty

efficient you can actually solve this

problem without keeping track of two

pointers you can get away with just

using one pointer so let's do that I

guess I'll leave it as previous and then

instead of current I'm going to say

previous do nextt because we know that

current was always one ahead of previous

anyway for current here I'm going to

change that again to previous do nextt

and to current here I'm also going to

change it to previous do nextt so now

this is just you know being shifted by

one here I'm going to change this to

previous do next and same thing here

actually I think I'm going a little bit

too much on autopilot because we don't

need to shift all of these so let me

delete this line and just reread what

we're doing here so if the next node is

one that we want to delete let's delete

it otherwise just shift the pointer I

think that's actually enough I don't

think we actually need anything else

since we only have one pointer anyway

and let me go ahead and run this and you

can see this one works as well I don't

think it's necessarily more efficient to

be honest um but the runtime says so but

if you found this helpful check out N.O

for a lot more I'm going to be launching

a free newsletter pretty soon it's going

to be covering data structures system

design and a lot more I'll also be

making a lot more system design videos

pretty soon I'm really excited about

that so subscribe if you want to see

those