4Sum II - LeetCode 454 - JavaScript
4Sum II - LeetCode 454 - JavaScript
Leetcode 454
#4sum #leetcode #javascript
Problem Link: https://leetcode.com/problems/4sum-ii/
Timeline:
0:00 - Reading the problem
2:36 - Key intuition
5:00 - Drawn explanation
12:15 - Code
Content
0.96 -> hello everyone today we're taking a look
3.12 -> at leap code problem number 454 which is
6.72 -> for some part two so you may have come
9.66 -> across problems like twosome in the past
12.42 -> and
14.099 -> um
14.639 -> the good news is that the key intuition
16.619 -> from problems like
19.08 -> two some will be used in this problem as
21.119 -> well and if you don't know what that
22.38 -> intuition is don't worry I'll be
24.119 -> touching on that in just a minute uh and
27.359 -> it's very very simple and this question
29.4 -> is is really much simpler than it looks
31.439 -> uh when you first try to take a crack at
34.26 -> it so let's try to understand what the
37.38 -> problem is actually asking of us
39.96 -> problem says that given four integer
42 -> arrays nums one two three and four
46.32 -> all of length n so they're all going to
48 -> be the exact same length return the
50.28 -> number of tuples such that all of them
52.739 -> are
54.18 -> greater than or equal to zero and less
57.239 -> than n so pretty normal is basically
60.48 -> saying that if you've gotten a certain
62.52 -> number of elements in the array this is
65.159 -> going to be 0 1 2 3. this is always
68.28 -> going to be less than four and it's
70.5 -> going to be greater than or equal to
71.88 -> zero if the N equals four so that's all
75.299 -> that's saying is fairly simple
77.24 -> so what else does the problem say
83.18 -> these indices must add up to zero that's
87 -> the other requirement so usually there
89.64 -> is a target provided in two sum or three
93.36 -> sum problems this one just doesn't have
95.82 -> a dynamic Target it just has a target of
98.88 -> zero
100.68 -> so that makes things a bit simpler let's
103.14 -> look at the first example
105.119 -> so they gave us again four tiny arrays
108.72 -> this this this and this and the indices
112.74 -> of zero zero zero and one add up to zero
115.979 -> so one minus two which is minus one
118.56 -> again minus one is minus two and then
122.04 -> minus two plus two is zero and they
124.56 -> found another instance of this happening
126.24 -> so pretty simple second example is even
128.94 -> simpler they have four arrays all of
132.239 -> them are single digit and they're all
134.64 -> obviously adding up to zero because they
136.319 -> are just zeros now the constraints let's
139.5 -> take a look at those it's always a good
141.06 -> idea to check those out uh
143.52 -> all the individual arrays are going to
146.64 -> be the exact same length so that's great
148.739 -> news uh number of items could be from
151.8 -> one all the way up to 200 and it could
154.62 -> contain negative values so now let's
158.7 -> let's go back to what I'd mentioned
160.44 -> earlier in the video which is the main
162.54 -> intuition
164.28 -> so the intuition from to some problems
167.519 -> just to give you a little bit of a
168.84 -> refresher or if you're not familiar just
171 -> to kind of brief you on what you should
173.4 -> know about problems like these so
176.04 -> if we're given an array just a single
178.019 -> array and asked to find two digits that
180.18 -> add up to a single number so let's say
182.64 -> in this case the array consists of two
185.04 -> three four five right just four items
188.76 -> and we're looking for a specific Target
191.879 -> which is
194.22 -> seven
195.3 -> now the very naive approach and uh and a
199.56 -> very complex approach in terms of time
201.659 -> complexity would be to look at the first
203.64 -> item in the array and then try to find
205.62 -> every possible combination of that item
209.4 -> and save any of those add up so in this
212.34 -> case we looked at this one we looked at
214.14 -> four we looked at five we're like okay
215.459 -> great we found a match but if you if you
218.819 -> give it some thought you realize that
220.319 -> the complexity of that is Big O of N
224.28 -> squared
225.9 -> with n being the number of items
228.72 -> in this array so if it's four items
231.48 -> we're easily looking at four squared
234.36 -> which is going to be 16. because that's
236.819 -> 16 possible combinations of each number
239.64 -> with another number so then the main
243.36 -> intuition and the main way to solve this
245.76 -> problem is to use a hash table because
247.92 -> if in a hash table we can just throw
250.799 -> these these items in so if we have 2 3 4
255.299 -> and 5 in a hash table
258.479 -> now when we go through these individual
261.12 -> items we're looking at two we know that
263.88 -> in order to get to a target of seven
265.259 -> we're gonna need a five so we just
268.08 -> simply go back to this hash table and we
270.3 -> ask it hey is there a five in here the
272.34 -> hash table goes oh yes there is here you
275.04 -> go and we know that we found ourselves a
277.56 -> match right same thing with when we look
279.479 -> at three we asked hashtag is there a
281.28 -> four in here it says yes sir we found
283.5 -> another match
284.699 -> right so that just really really simple
288.18 -> simplifies the entire complexity and
290.28 -> brings it down to O of n we're only just
293.28 -> doing this operation for the number of
295.32 -> individual items uh in the array
298.56 -> so
299.88 -> this problem is a bit different though
301.56 -> because not only do we have four
304.199 -> different arrays uh the target stays the
308.1 -> same it's always zero and you'll see why
310.979 -> uh that leads to a bit of a
313.08 -> simplification later on which is going
315.36 -> to help us out so I remember thinking
317.94 -> about this to myself and thinking that
320.34 -> if the the naive approach of having only
324.18 -> one array and trying to find a Target is
327.419 -> N squared because you're looking to find
329.94 -> n times n combinations with this it
332.52 -> could actually get a lot worse because
333.84 -> now let's say we've got the same arrays
336.96 -> as we have in this example so we have
339.32 -> one and two we have minus two
344.22 -> and -1
347.759 -> and we also have
349.68 -> minus one and two
352.44 -> and zero and two
355.5 -> now we know we're gonna have to touch
357.78 -> all these items individually there's no
359.699 -> way around that now how do I actually
361.979 -> figure out what the best path is because
364.02 -> I'm almost thinking about this like a
365.46 -> path so I could start here and then I
368.34 -> could go here and then from here I could
371.039 -> go here and from this point maybe go
374.82 -> down to here does that work one minus
377.28 -> two minus one and then again minus two
380.88 -> zero no that didn't work so then I start
382.74 -> again here and then I go down here like
385.68 -> that is really starting to add up and
387.9 -> ultimately you realize this is actually
391.259 -> and fairly complex this is Big O of n to
395.16 -> the power of four so knowing that this
398.52 -> can be up to 200 items as we know from
401.1 -> the constraints
402.539 -> that's that could be a really really
404.1 -> complex program so is there a simpler
406.74 -> way to do this like how do we actually
408.84 -> simplify this uh for ourselves and the
413.039 -> thought that I had that made me move
415.08 -> forward in this function is hey I don't
416.699 -> know I don't know how I do a four thumb
418.5 -> simply but maybe I could just do a two
421.199 -> sum twice why could I do that and the
425.039 -> answer is yes you can uh and this is a
428.1 -> little bit of how that would work so I'm
430.38 -> going to move this out of the way
432.06 -> let's move this
433.62 -> to the left and create some space in the
435.96 -> middle and the way that this is actually
439.02 -> possible for us and the way we can
440.639 -> actually make it happen is we simply
443.52 -> create instead of one hash table
446.639 -> we create two hash tables
449.639 -> so we'll have one on the left and one on
452.22 -> the right and what this hash table is
454.56 -> responsible for is to store the sums of
458.34 -> just these two arrays that are on top of
460.979 -> each so hash table number one
463.56 -> is in charge of these two arrays and
466.74 -> hash table number two is in charge of
469.919 -> these two arrays and we know that within
473.28 -> this there are
474.78 -> o and squared sums and same with this
479.46 -> well luckily o n of 4
484.44 -> and o n
486.539 -> squared plus O N squared
491.639 -> these are not really the same this is
494.099 -> actually much better for example if
497.4 -> we're looking at
499.379 -> let's say three because n to the power 4
503.099 -> in the case of three items would be 81.
508.68 -> but n to the power of 2
512.159 -> times 2 would be in the case of 3 again
515.76 -> 9 times 2 18. so there's a pretty
518.039 -> massive difference in these two ways to
520.919 -> solve this problem so how does this
522.839 -> actually work within this hash table
524.82 -> what we do is we store a specific number
527.04 -> of combinations so
529.38 -> 1 plus minus two that is minus one and
533.76 -> the second is one minus one okay that's
536.94 -> a zero now what else do we have we have
539.58 -> two minus two so that is zero again so
542.94 -> instead of adding another zero to this
545.1 -> hash table what I'm actually going to do
546.36 -> is I'll just go ahead and say zero
549.779 -> occurs twice so let's start saving the
552.66 -> number of instances and by default this
554.58 -> will be a one zero occurs twice and the
558.12 -> last one is going to be
560.899 -> 2 plus minus 1 which is basically one
566.519 -> so one also appears
569.1 -> just once
572.22 -> and change the color on that
578.94 -> so that's our first hash table the
580.92 -> second one exact same approach let me
582.959 -> get through this quicker so minus one
584.82 -> plus zero is
586.68 -> minus one
589.08 -> and then minus one plus two is one
594.36 -> 2 plus 0 is 2 and 2 plus 2 is 4. all of
599.76 -> these are showing up just once we had no
601.86 -> repeats one one one
605.36 -> and one
607.14 -> now all we're doing is doing the exact
610.8 -> same thing as we did
613.2 -> before but now with these two hash
615.66 -> tables so we look at every single value
617.459 -> in hash table number one and we know
619.44 -> that hey when we're looking at minus one
622.32 -> in order for it to get to zero we're
625.68 -> gonna need a one so when we're at minus
629.459 -> one we check hey does this other hashtag
631.14 -> we'll have a one great yes it does and
634.08 -> this is where having stored the number
636.66 -> of instances actually helps us because
638.7 -> in this case one just appears once so we
642.42 -> change the number of results to one and
645 -> we're going to keep incrementing this
646.26 -> counter as we go uh when we're looking
649.38 -> at zero so in order for zero to work out
652.079 -> we need another zero unfortunately
653.94 -> there's no other zero in this then we
656.459 -> look at one for one to work out we're
658.86 -> gonna need a minus one do we have a
660.3 -> minus one yes we do so then we have a
662.88 -> two now the only other instance the
666.06 -> other only other possibility would be if
667.8 -> minus one actually appeared twice so
670.56 -> let's say for example one of these
672.66 -> numbers instead of it being
674.94 -> um you know
676.38 -> it was
678.42 -> I can't think of a good example but
680.339 -> let's say this was instead of two and
682.62 -> zero it was a minus three so two and
685.14 -> minus three is minus one now if that was
687.42 -> the case uh in addition to minus one and
690.12 -> zero this would have been two instances
692.04 -> of minus one and instead of adding just
695.16 -> one more here we would have added two
697.98 -> more because one plus minus one is zero
700.86 -> minus one appears twice we have three
703.8 -> possible combinations and that would
705.48 -> have been the result
706.86 -> so in summary the way that we're solving
710.22 -> this problem is we are effectively doing
712.38 -> a two sum but we're doing it
715.74 -> twice so we find these results we find
720 -> these results and then we try to make a
723.36 -> match happen and in this case it was
726.24 -> just 2 which is the same as the example
729.779 -> provided above
731.339 -> and that's it now let's go ahead and
733.98 -> jump into the coding
736.2 -> what I'm going to do is I'm going to
737.399 -> start off by initializing a variable
740.459 -> called length I feel like I'm going to
743.16 -> be referring to the length on a number
745.5 -> of different occasions when I go through
746.94 -> my Loops so I just want to start off by
748.92 -> saying length is going to be let uh nums
752.339 -> one dot length so I'm going to come back
754.5 -> to this variable in a second uh and
757.8 -> let's go ahead and initialize those two
760.2 -> hash tables that we're going to be using
763.8 -> so let first two which is the first two
766.86 -> arrays uh the hashtag will contain the
769.56 -> first two arrays equal new map and let
772.44 -> second two
774.48 -> equal new map as well
779.519 -> now
780.899 -> what we're going to be doing is what we
782.7 -> just described in the drawing as going
784.92 -> through two arrays at a time and storing
787.74 -> their sums and the number of times those
789.42 -> sums appear into this hash table so I
792.3 -> know that's going to happen twice so why
794.639 -> not just write a function for it and
796.2 -> then call it twice with the right
798.2 -> parameters containing those two arrays
801.06 -> and the appropriate hash table to which
803.88 -> the function needs to add the values
806.22 -> let's go ahead and write that so I'll go
808.44 -> ahead and call that function add to map
812.18 -> and my parameters will be nums a so the
816.06 -> first set of the first array of values
819.36 -> nums B and the map to which it's going
823.019 -> to get stored
824.24 -> and for now we're going to need a for
826.44 -> Loop so let's go ahead and this is the
828.6 -> part where we use that variable that
830.639 -> we've stored earlier let I equals zero
833.459 -> let's save us some characters and I is
836.7 -> less than length
838.44 -> create some spacing make this a little
840.3 -> bit more legible
841.62 -> and
843.66 -> I plus plus
845.339 -> so that will be our first kind of layer
847.62 -> of the for Loop the second one is going
850.019 -> to be for let J equals zero
855.12 -> you know add some space here for the
857.04 -> sake consistency
859.019 -> and J is less than length exact same and
864.66 -> J plus plus
866.82 -> at this point I'm going to describe a
869.279 -> new variable that basically is a bit of
871.56 -> a checker for me to see if this value
874.26 -> that I'm about to add already exists in
876.18 -> the hash table so we'll just do map dot
878.76 -> get so map being the specific map that's
880.92 -> been passed to this function
882.8 -> nums a
885 -> I
886.32 -> plus nums B J so we know this is going
891.18 -> to be o n to the power of two that's
893.639 -> okay we're just going to do that twice
895.56 -> so we know that's not that bad I have a
897.779 -> bit of a nested Loop here but
899.699 -> it's been accounted for
901.32 -> map dot set
903.48 -> and what we're setting here is nums a
909.48 -> I
912.12 -> plus nums B
914.579 -> J
916.019 -> and
917.279 -> this is where we use the getter so if
919.019 -> getter already exists like there is a
920.94 -> value that's already stored then all
922.74 -> we'll do is we're just going to go ahead
924.12 -> and increment that value so if a zero is
925.92 -> already stored you know tell the map
928.32 -> that it appears twice so not just once
930.959 -> otherwise just go ahead and assign it a
933.3 -> one zero appears once for example we
936.3 -> will call this function twice so let's
939 -> call it for the first two arrays so nums
942 -> one
943.38 -> nums two and we need these added to the
946.68 -> first two map and we'll call it again
950.339 -> nums three
952.26 -> nums four and we want this added to the
955.199 -> second do map so all of the sums have
958.62 -> been added so have been uh their
960.779 -> instances the number of times they
962.16 -> appear now
964.199 -> we're gonna need
965.94 -> a return count like this is the count
968.279 -> that we're going to return at the end of
969.48 -> the function so I'm just going to go
970.56 -> ahead and start that at zero
972.779 -> and
974.279 -> at this point we're going to go through
977.1 -> each and every entry of first two to
980.579 -> find and check for any matches so go
982.38 -> through every entry
984.72 -> of first two the Mac or the hash map we
987.6 -> have at the top and
989.88 -> report any matches
992.94 -> seeing as we need to find sums that add
995.399 -> up to zero so first two dot four each
999.06 -> these are four each
1001.579 -> and we're going to need the values and
1003.56 -> the keys
1005.72 -> partner function let getter again I just
1008.899 -> like the word getter
1010.339 -> second two dot get so now based on the
1014.06 -> value that we're looking at right now
1015.98 -> for first two look at the second two dot
1019.82 -> get
1021.56 -> key
1024.799 -> times minus 1.
1029.6 -> basically if we're at a 2 like this is
1033.14 -> the main kind of helper of
1035.959 -> um having zero as a Target if the sum
1038.72 -> that we're looking at in first two is a
1041.54 -> two we know we're going to need a minus
1043.699 -> two in the other one for it to add up to
1046.28 -> zero right nothing else
1048.5 -> there's really no no advanced math meter
1050.72 -> here and if we don't have the exact
1053 -> opposite of it like if if we have a
1055.88 -> minus two then we're going to need a
1057.38 -> plus two uh then that sum of zero is not
1060.679 -> going to happen so that's what getter is
1061.88 -> going to check for and if getter exists
1065.179 -> go ahead and increment return count by
1069.74 -> getter times the value so this is
1073.58 -> necessary because if we have two uh
1076.82 -> zeros for example in in second two and
1080.36 -> we were sitting on
1082.22 -> um
1083.66 -> you know we had a zero in first two as
1085.88 -> well now we know that's two possible
1087.74 -> matches and not just one so we're gonna
1089.84 -> add two instead of one otherwise the
1092.84 -> value is always going to be uh
1095.059 -> just one so we'll increment by one uh if
1098 -> it's just one instance and in the end
1099.98 -> we're going to return the return count
1102.98 -> so
1104.299 -> that's basically it for the code we'll
1106.34 -> go ahead and submit that
1111.32 -> and it looks like I made a mistake
1113.84 -> ah I made a bit of a typo here
1118.22 -> and let's go to submit that now
1123.86 -> there we go so uh fairly efficient
1128 -> function and uh that's it for this
1130.64 -> problem
1131.48 -> I hope you guys like the video and be
1133.34 -> sure to subscribe for similar content
1135.26 -> like this I'll be solving more legal
1136.76 -> problems and see you in the next one
1138.5 -> take care
Source: https://www.youtube.com/watch?v=sbw8rmxVcX4