Two Sum - Leetcode 1 - HashMap - Python

00:00

let's all leak code one to some the most

00:02

popular leak code question so we're

00:04

given an input array and some target in

00:07

this case 9 and we want to find the two

00:10

values in this input array that sum to 9

00:12

so in this case it's 2 & 7 now we want

00:15

to return the indices of these two

00:17

values so the index of zero of the index

00:20

of two is zero the index of 7 is 1 so we

00:22

return 0 & 1

00:24

we're guaranteed that there's exactly

00:26

one solution so we don't have to worry

00:27

about not finding a solution and we

00:30

don't have to worry about multiple

00:31

solutions now the most intuitive way to

00:33

solve this problem is basically just

00:35

check every combination of two values

00:38

and see if they can sum up to our target

00:40

so we start at 2 we check every

00:43

combination we can make that includes 2

00:45

so we scan through the remainder of the

00:48

array 1 5 3 and check if any of those

00:51

numbers added to 2 some store target for

00:54

in this case none of them do so next we

01:00

can repeat the process

01:01

let's check every combination including

01:04

one that sums up the target for so we

01:06

scan through every element that comes

01:08

after at 5 & 3 and we find that one

01:12

added with 3 sums up to our target 4

01:15

notice that we didn't have to check the

01:18

values that came before 1 because we

01:20

already checked the combination 2 & 1

01:22

when we were up over here remember when

01:24

we checked every combination with 2 so

01:27

we didn't have to repeat that work down

01:29

here we only had to check the numbers

01:30

that came after 1

01:32

so the runtime of this algorithm isn't

01:34

super efficient this is basically brute

01:36

force we're going through the entire

01:38

array of length and and we're gonna do

01:40

that worst case n times for each number

01:43

this means that over all worst case time

01:46

complexity will be O of N squared so can

01:49

we do better now the thing to notice is

01:51

that for each number for example 1 the

01:56

value we're looking for is the

01:58

difference between the target and this

02:00

value 1 so we're looking for 4 minus 1

02:03

which is equal to 3 so that means this

02:06

is the only value we can add to one

02:09

that'll equal the target so we don't

02:11

have to check every number we just want

02:12

to know if

02:13

resist s-- now the easiest way we can do

02:15

this the most efficient is by making a

02:17

hash map of every value in our input

02:20

array so we can instantly check if the

02:22

value 3 exists now let's try the same

02:27

problem except let's use a hash map this

02:29

time now in our hash map we're going to

02:36

be mapping each value to the index of

02:39

each value so the index of 2 is 0 the

02:42

index of 1 is 1 the index of 5 is 2 the

02:44

index of 3 is 3 so let's so in our hash

02:47

map we're going to be mapping the value

02:49

to the index

02:55

now we could add every value in this

02:59

array into the hash map before we start

03:02

iterating through it but there's

03:03

actually an easier way to do it if we

03:06

added the entire array into the hash map

03:08

initially then we would get to the value

03:10

2 first right we would want to checked

03:12

as the difference between target 4 minus

03:15

this value 2 which is equal to 2 exists

03:18

in our hash map and we would find that 2

03:21

does exist in our hash map but we're not

03:23

allowed to reuse the same one right

03:26

because they're both at the same index

03:28

we can't use the same value twice so we

03:30

would have to compare the index of our

03:32

current 2 with the index of the 2 that's

03:35

in our hash map there's actually an

03:38

easier way to do this though and it's a

03:39

little clever and let me show you how to

03:41

do it that way so doing it this clever

03:43

way initially we say our hash map is

03:46

empty so we get to the value 2 first of

03:48

all right and we want to look for the

03:50

difference 4 minus 2 in our hash map our

03:54

hash map is empty so we don't find 2 so

03:57

then after we visited this element then

04:00

we can add it to our hash map so now

04:02

that I'm done visiting it I'm gonna move

04:04

to the second element 1 and before I do

04:07

that I'm gonna add this value 2 to our

04:09

hash map and the index of this value is

04:12

gonna be 0 now I'm at 1 I'm looking for

04:15

4 minus 1 which is 3

04:18

I see 3 isn't in our hash map but it

04:21

actually is in our array so what's the

04:23

problem well for now we're going to say

04:25

we don't find our find

04:27

three so we add one to our hash map the

04:29

index of this one is one and now we move

04:33

to the next element five we check does

04:36

four minus five it's four minus five

04:39

exists in our hash map that's negative

04:42

one so no it does not then we add this

04:44

five to our hash map and it's index

04:47

which is two and we move to the last

04:51

value in the array three we checked this

04:54

four minus three e

04:56

exists in our hash map now that's one so

04:59

we see it does exist right right over

05:03

here it exists the value exists and it's

05:06

index is one so now we found our two

05:10

values that sum to the target and we

05:12

want to return their indexes their

05:14

indices which are going to be one and

05:16

three so with this algorithm we don't

05:21

have to initialize our hash map it can

05:23

be initially empty and then we can just

05:25

iterate through this array in one pass

05:28

now the reason the algorithm can work in

05:30

that way with just one pass is this so

05:34

let's say we had a giant array right we

05:37

know for sure that there are two

05:40

elements in this array that sum to our

05:43

target right we don't know where they

05:45

are they're at some arbitrary location

05:47

when we visit the first one of those

05:49

elements our hash map is only going to

05:52

be this portion of the array it's only

05:55

going to have the values that came

05:57

before the first value so we're gonna

05:59

we're gonna notice that the second value

06:02

that can sum to the target is no is not

06:05

going to be in our hash map yet but once

06:08

we get to the second value our hash map

06:11

is going to be this portion so every

06:14

value that comes before this right so

06:17

we're gonna be guaranteed that once we

06:20

visit the second element that sums up to

06:22

the target we're gonna be guaranteed

06:24

that the first one is already in our

06:26

hash map so we're guaranteed to find the

06:29

solution now since we only have to

06:31

iterate through the array once and we're

06:34

adding each value to our hash map which

06:36

is a constant time operation and we're

06:38

checking if a value exists in our hash

06:40

which is also a constant time operation

06:43

the time complexity is going to be Big O

06:45

of n we are using extra memory right

06:47

that hash map isn't free so the memory

06:50

complexity is also going to be O of n

06:52

because we could potentially add every

06:54

value to the hash map

06:55

so now let's code the solution so

06:57

remember we need a hash map right I'm

06:58

going to call this previous map because

07:00

it's basically every element that comes

07:02

before the current home that every

07:04

previous element is going to be stored

07:05

in this map where it can be mapping the

07:07

value to the index of that value

07:10

so now let's iterate through every value

07:13

in this array we need the index as well

07:15

as the actual number so let's do it like

07:18

this and Python before we add this to

07:24

our map let's check if the difference

07:26

which is equal to target minus n now

07:30

let's check if this difference is

07:32

already in the hash map if it is then we

07:40

can return the solution which is going

07:42

to be a pair of the indices so I can get

07:49

the first index like this and the second

07:52

index is just AI now if we don't find

07:54

the solution then we have to update our

07:56

hash map so for this value n I'm gonna

08:00

say the index is I and then we're going

08:03

to continue since we're guaranteed that

08:05

a solution exists we don't have to

08:07

return anything out here right but I'll

08:09

just put a return for no reason now

08:11

let's see if it works and it works

08:14

perfectly so with this kind of neat

08:16

little trick but just doing it in one

08:18

pass you can reduce the amount of code

08:20

you have to write and not have to worry

08:21

about like edge cases and comparisons

08:24

and things like that