- Coding Videos/
- Node.js /
- Node.js/JavaScript interview training – Largest rectangle and water trapped

# Node.js/JavaScript interview training – Largest rectangle and water trapped

### Download Video link >

Node.js/JavaScript interview training – Largest rectangle and water trapped

I’m solving typical coding problems you would be asked to solve during an interview. These puzzles are a lot of fun and there’s always something new to learn.

* Largest Rectangle in Histogram: Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

* Trapping Rain Water: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Glitch project to visualize a histogram: https://histogram-from-array.glitch.me/

Source code on https://github.com/fhinkel/twitch. — Watch live at https://www.twitch.tv/fhinkel

source

### View Comments source >

### Transcript view all >

00:00 hello happy Saturday how are you today

00:04 oh hey Julian how you doing today

00:08 alright I got some really cool problems

00:11 for a cheat day so let's get right

00:15 started the first one is given an ngon

00:19 netiquette negative integers

00:21 representing the histograms bar height

00:23 with the width of each bars 1 find the

00:26 area of the largest rectangle in the

00:28 histogram alright so those are super

00:31 hard to understand without the picture I

00:33 think so here's an example the input is

00:36 an array with these six entries they're

00:38 all non-negative integers and you can

00:41 think of these integers as representing

00:44 the height of bars in a bar graph or

00:46 histogram and you're supposed to find

00:48 the largest rectangle the area of the

00:51 largest rectangle that you can fit into

00:53 this histogram so what I actually did

00:57 yesterday we acquired is I was using

00:59 glitch glitch calm super cool you can

01:02 make a website with even back-end if you

01:04 want but I only just need a front end

01:06 and you can go yeah here's the Edit

01:10 project so this is where you have your

01:14 source code my index.html and my script

01:19 jeaious and then you can show it live

01:22 and you can share this link with anybody

01:24 so if you want you can try this out

01:27 right now and what this cute little

01:31 website does is it draws a histogram

01:34 given an array so if you give it some

01:36 numbers it draws you this histogram so

01:39 say we have the numbers 3 4 5 6 8

01:43 dropped down to 1 9 5 then this is the

01:48 histogram we would get all right there

01:51 so we have an array it represents a

01:54 histogram and we are now supposed to

01:56 find the area of the largest rectangle

01:58 that can fit here so one rectangle you

02:01 could fit is if you used one that is

02:05 like flat on the ground it goes all the

02:07 way across all six entries but it can

02:10 only have height one because this one

02:13 he's so short so if you had the one all

02:15 the way on the ground going all the way

02:16 over it would have area six or you could

02:19 have one that has height too but then it

02:22 doesn't fit right here so it would go

02:24 from here over to here does that kind of

02:27 make sense and then that one would have

02:29 with four and height you so area eight

02:32 and now the largest one you can fit in

02:35 this particular input has area ten that

02:39 is if instead of having it flat on the

02:40 ground we flip it upside down and we fit

02:44 it here including the second and third

02:48 bar or the third and fourth bar depends

02:51 on if we count like humans or computers

02:53 and then we can go all the way up to

02:55 height 5 so you can get 2 times 5 which

02:58 has area 10 in here all right so given a

03:03 bunch of numbers that represent a graph

03:05 like this we're supposed to find the

03:07 largest histogram possible how should we

03:11 do this and this is a very typical

03:14 interview question that you might get

03:16 asked doing the phone interview or the

03:19 on-site interview and ideally your

03:24 interviewer would give you an example

03:25 and they'd also give you a picture

03:26 because without the picture this is

03:28 really hot but you imagine and

03:30 especially if it's a phone interview you

03:31 can't share a drawing like of course you

03:34 can have a piece of paper with you and

03:36 sketch something for yourself but you

03:38 always want to show that you can

03:40 communicate and you also want to make

03:41 sure that what you're drawing and

03:43 communicating is right so if your

03:44 interview I can't see that that would be

03:46 really back so if you get a problem like

03:49 this in an interview there's probably an

03:51 image with it and an example input

03:55 alright so how can we do this so one

04:03 option is we could take every element

04:09 here as a starting point and also every

04:13 element on the right of it as an end

04:15 point so n time in starting and point

04:23 areas and then always find the max

04:26 mom height that we can go to so that's

04:28 the minimum of the bars over that and

04:31 calculate the product of it should we do

04:35 that that's not a very fast solution but

04:38 it's a correct solution it's pretty

04:40 straightforward and so at least you get

04:42 something on the paper and then once we

04:44 have that we also have something to test

04:48 our answer egg against because I only

04:50 have this one test case so far so once

04:53 we have that we can then think about

04:55 fastest solutions all right well let's

04:58 do that all right

05:03 so Const I wonder if I should turn off

05:10 the Crocker extension or if it's helpful

05:14 so cons largest rectangle is a function

05:21 that takes an input array and it's

05:24 supposed to return the maximum area

05:28 well max area equals 0 return max area

05:34 all right

05:36 so for what I equals 0 I less than 8 at

05:41 length I plus plus and actually I don't

05:45 want to call it I I want to be a little

05:47 more explicit so let's call it left so

05:51 for every last one we also want do you

05:55 guess that a right one we're right is

05:58 left plus 1 right less than eight at

06:04 length right plus plus let me just think

06:09 whether this should start at the same

06:12 spot I guess it should start at the same

06:14 one because you could have boss that

06:16 just have height 1 right all righty

06:21 oh hi Kai I'm so glad I figured out how

06:26 to say your name how's it going how's

06:29 the weather in Germany

06:34 all right so we going from left to right

06:37 and now for every left to right we need

06:40 to find the height that we can use for a

06:43 rectangle so we need to find the minimum

06:47 minimum equals number charge positive

06:53 infinity thank you so much every single

07:04 time I get this wrong okay that would

07:07 have been very confusing because we

07:09 would never run this loop all right so

07:12 for glad I equals left I left and right

07:19 I plus plus no equal right minimum

07:29 equals master minimum of the old minimum

07:32 and the height at that position and then

07:38 let area equals the minimum x right

07:45 minus left and I think I have to add one

07:49 here so because I'm starting let's think

07:56 this through if we are on the end

07:57 element on the last one we still want

08:00 that bar that has height one so I need

08:03 to like add one here and then of course

08:06 the max area is method max of area and

08:11 max how does that look so we take the

08:18 array and we take every last point and

08:20 then we take every possible right point

08:23 so we're taking every possible interval

08:28 in this whole array and then we find the

08:34 smallest paragraph in that is the

08:38 rectangle that fits over the length of

08:41 this interval it can't be higher than

08:43 the smallest bar graph we calculate the

08:46 area

08:47 we opted max area

08:52 oh hi recursion while your name's really

08:55 fitting here welcome I hope you enjoy

08:57 this alright let's try it

09:01 largest rectangle on this here our max

09:09 is not defined because it is max area

09:16 also that like this perfect so this

09:21 seems to be quite correct should we try

09:23 a few other examples let's throw in a

09:28 zero here just for giggles and see if

09:33 the area really is 6 so let's draw this

09:38 one so what's the highest area we could

09:41 get we could go all the way up here then

09:43 it's 6 or if we go over here it's 6 as

09:46 well everything else is smaller ok that

09:49 looks good

09:51 what's another one what if we go higher

09:54 here let's make sure it goes all the way

09:56 up to the top so instead of a 6 I want

10:00 an 8 here and then

10:03 yep the highest area would be this one

10:05 everything else is smaller okay that

10:08 also seems correct anybody have a good

10:11 array we should test and really think we

10:13 have some edge cases oh I know one let's

10:17 make sure the last one is actually used

10:19 ok you think this is being used let's

10:24 make sure we have fun yep so if we go to

10:27 the side that also seems to work let's

10:31 just double-check the picture

10:38 okay so you're the picture we're going

10:41 to four six eight ten twelve fourteen

10:45 should be the answer yes that looks good

10:48 and I was trying this one here alright

10:51 so this one's 10 6 8 14 okay

11:03 what's the complexity of this one so are

11:05 we going from left to right that is

11:07 linear complexity but then inside this

11:09 loop we're also going from right to the

11:13 end so that is n times n so we already

11:15 quadratic but sadly now we're iterating

11:19 another time here over all those in the

11:23 interval so we have cubic complexity so

11:29 this one is oh and you 2/3 all right so

11:36 that's probably a little too slow I mean

11:39 it worked fine on our examples here once

11:42 you have something bigger eventually

11:44 it'll slow down well I can't write an

11:47 area but if we had like randomly

11:49 generated one so say we had 100 elements

11:55 in the array then the complexity would

11:58 be a hundred to 2/3 so want to want to

12:03 want to can't even beat that number so

12:06 it would take a million iterations and

12:08 if we had a thousand it would be 1 2 3

12:11 extra zeros so for N equals a thousand

12:14 this was already probably be quite slow

12:17 all right can we make this bad

12:25 so what's another way we could think

12:29 about this

12:41 another way we could think about it is

12:44 if we take every bar by itself and we

12:50 say okay this bar should be the height

12:53 of the rectangle what can we fit here so

12:56 what correct angle can we fit here that

12:58 has height you well only this small one

13:01 now for this one what can we fit here

13:03 that has height 100 the way over what

13:06 can we fit here that has height for well

13:09 these two then for height six it's just

13:11 one bar here what's a rectangle of

13:14 height 2 okay so it's over of length 4

13:19 ok and then for height 3 again it's a

13:22 with what so how how would I coat this

13:28 what I just said in my head well I take

13:31 every bar I iterate over them and then I

13:33 go to the left and to the right and I

13:36 find the first bar that is too small

13:38 that is smaller than the bar I already

13:40 have and that gives me the left and

13:43 right marker for that rectangle I

13:45 calculate the area and then keep track

13:48 of the maximum and the complexity for

13:52 that is not going to be cubic it's just

13:55 quadratic so we already saved a ton of

13:57 time because we started with a really

13:58 slow solution but this is much better

14:00 than a cubic solution um we go through

14:03 linearly and then for every single one

14:05 we searched a minimum on the right and

14:07 on the left Highness duska thanks for

14:13 the following how's your Saturday going

14:20 ok all right let's start over

14:26 so Kahn's watch this rectangle quadratic

14:32 again as a function that takes an array

14:36 and just like before we have a

14:41 max area and we want to return that max

14:45 area so now the algorithm we had was we

14:49 said or we iterate over all the bars so

14:54 for what I equals zero I less than a

14:59 that likes no type of this one time

15:02 thanks Kai for correcting me the first

15:04 one I would have been debugging for

15:06 quite a while

15:07 all right so we need to get the left one

15:13 and the right one

15:15 but first height is a of I and now while

15:26 left left is equal to I so while left is

15:34 bigger than 0 if a left is less than the

15:47 height then we want to break that right

15:52 so as long as we and of course we have

15:58 to move to the left so left - - so now

16:03 while it is bigger or equal to 0 and the

16:10 same for right so while right is less

16:17 than 8 links if a off right if that is

16:25 smaller than the height we want to break

16:29 height of Maxie a thanks for the follow

16:31 much appreciate it

16:37 no I will not work on the a down the

16:40 stream I'm not under the ATM anymore I'm

16:42 on the GCP Google cloud platform team

16:45 now so there might be some GCP stuff I

16:50 was the thing I would imagine that it's

16:52 really hard to follow somebody

16:55 King on v8 because you don't have a

16:56 contained problem like in these

16:59 interview questions and you might also

17:01 notice my font here is really big so

17:04 that it's easy for people to see and if

17:07 I had anything more complex than an

17:09 interview question I couldn't work

17:11 efficiently was just such a big font I

17:14 would need to have more information on

17:16 the screen and then I think it would

17:18 just be really hard to stream that and

17:24 you believe there's some Firefox

17:26 engineers though who stream some of

17:29 their work you should check them out

17:35 there's a few places Firefox engineer

17:43 coding yeah so my Conway hacks on

17:55 Firefox stuff you're looking for streams

17:58 to watch this reddit watch people code

18:05 yeah live programming streams so some

18:08 people announce this stream here and

18:09 then there's also I'm gonna say ship

18:14 stream yes ship stream so that's another

18:19 website oh yes I'm real life right now

18:22 showing ship stream ship stream inside

18:25 ship stream awesome okay yeah but

18:28 there's different people you can follow

18:30 and then of course if you're on Twitter

18:35 and you search for what's the best thing

18:40 to search for and Twitter like twitch

18:42 life coding also yeah why doesn't that

18:57 come up as a Twitter user

19:06 so Oh weird okay I was gonna say they

19:11 work at Twitter I misspelled the name

19:15 Emily burrows do work at twitch and they

19:19 can tell you about a few other coders

19:21 [Music]

19:24 hey entrant coder how's it going it's so

19:27 kind of morning here but good afternoon

19:29 to you miss Jetson

19:32 Oh Landru okay thank you yes

19:41 so they work at twitch and they a lot of

19:44 times tweet about cool people that do

19:46 life coding so that's another way to

19:48 find a few other streams all right back

19:52 to work so right as I and we have to

19:57 move right to the right to find the

19:59 minimum and now that we have left and

20:03 right we want to say the area is height

20:09 x right minus left and now just a few

20:15 off-by-one errors maybe so there's one

20:26 that's the first one that's true small

20:28 and this is the first one yep those are

20:31 both the first ones that are too small

20:33 so for this one year the first one too

20:36 small would be at index 1 and T either

20:39 first one too small what P at index 4 4

20:42 minus 1 is 3 but we only want with

20:45 cheese so we have to subtract 1 here and

20:49 then we have to update max area is

20:54 Method max max area and area

21:07 yeah there's a bunch of design documents

21:10 this blog post mostly you just really

21:12 have to dig into the code though it's

21:16 hard to get complex concepts into a

21:19 readable design document and also stay

21:23 up to date with the documentation all

21:27 right

21:28 so how should we test this we can just

21:37 copy and paste these test cases and

21:41 [Music]

21:43 largest rectangle what did I call it

21:49 what okay and that still seems very

21:57 correct right all right let's make sure

22:02 this all makes sense and why this is

22:04 quadratic so we're going through every

22:10 bar and we take two height for that bar

22:14 and then we set a marker at that same

22:20 bar and why we have space to the left we

22:25 keep moving left until we drop down from

22:29 the bar so here's moving left and we do

22:31 the same to the right we move to the

22:33 right until we hit something that has

22:36 two less of a height and then the area

22:38 is the height of the bar that we started

22:40 with and then right minus left the space

22:44 between those two update max area all

22:47 right so we went from quadratic from

22:51 cube to quadratic so if we had a hundred

22:55 here we would 10,000 if we have a

23:00 thousand we would only need a million

23:04 iterations heiping who was the go for

23:12 JavaScript developers is having

23:13 happening on Tuesday in a week

23:16 on the 19th I wanna say what day is

23:19 today 9 yeah so in 10 days

23:23 a little later it's around 3 or 4 p.m.

23:26 so it's 11:00 in the morning right now

23:30 so a few hours later and I'm doing it

23:34 together with Andy burns who is on the

23:36 go team at Google very excited about

23:38 that one that should be fun I've never

23:40 done much go I think I've tried a few

23:43 hello words but never needed it so never

23:46 learned anything but it'll it'll be fun

23:48 to work on that together all right

23:51 so we have this let's just be good

23:54 citizens I'm committed and three can I

24:09 have these symbols and a commit message

24:13 I can't cool how cool you're learning it

24:17 right now do you also have a JavaScript

24:18 background or what's your background oh

24:29 okay yeah cool

24:31 yeah those exercises are always a good

24:33 starting point to learn if you so

24:36 anything really cool I have a really

24:38 cool extension or polygon or something

24:42 let us know in the next stream and we

24:45 can see yeah I would like to know about

24:48 any tips thank you okay so right now

24:51 these tests are very manual and they

24:53 also gonna start looking very messy soon

24:56 so why don't we write a test function

25:00 [Music]

25:05 that's right a test function that takes

25:08 an array and it should compute that quad

25:18 equals largest rectangle quad look Q

25:24 largest rectangle

25:26 [Music]

25:29 if is not equal to Q console.log no

25:45 Monty Airy and then what is not equal to

25:59 cube and just make sure we see it

26:03 through now let's call test cannot read

26:14 the length of undefined already okay

26:19 this seems to work well should we just

26:24 use random things here okay okay so as

26:41 soon as I have a working array

26:44 everything's good okay let's make

26:59 another test helper random area is a

27:05 function that should generate a random

27:07 area of length M and we won that a is an

27:15 array for I equals 0 I list and I plus

27:22 plus a that push math.random multiplied

27:34 let's go with numbers up to a thousand

27:40 and how do I brown something to a number

27:47 do i just use mastered floor or silica

27:50 now yeah master floor should be fine

27:54 so master floor we turn that one so here

28:02 we want to run the test a random array

28:08 of twenty elements and I just want to

28:13 see that dad looks like a random array

28:20 right looks good for us looks good

28:22 enough I'd say Oh should we time should

28:35 be time this may at some point this

28:53 should like stop printing here right oh

28:58 now it's running running running running

29:00 running okay so this is why it's slowing

29:03 it down should we print out I don't how

29:04 long it takes this is how I'm doing it

29:22 console.log dreading for edit length

29:38 elements took after -

29:47 before / it's I was seconds idea smaller

30:10 numbers here otherwise coca is gonna get

30:13 very confused yes I think Coco will get

30:17 confused after Kubik for an element's

30:35 took this long maximum rectangle after

30:45 has already been declared okay that's

30:55 not how I wanted my seconds to be so we

30:58 do after - before which should be

31:01 milliseconds that seconds equal

31:23 and we want master what am I doing wrong

31:34 here so before the date after acetate

31:42 before equals yeah

31:57 how am I getting these big numbers

32:00 before after sto typos and before and

32:03 after maybe

32:30 oh sorry bodice deleting everything you

32:44 wrote sorry about that oh you say I

32:50 should use performance that now instead

32:52 of data now what's the difference

32:55 between performance and dated now again

32:58 but this should also work what's wrong

33:02 here oh I see what's wrong

33:10 alright see what's wrong alright yeah

33:17 it's more precise ok yeah yeah so that

33:34 looks more maked and now if we go up to

33:37 I think it was 20,000 when I started

33:41 seeing problems on our problems but like

33:45 it and noticeable slowdown so let's see

33:47 how long this takes

33:54 yeah in in such a silly benchmark it

33:56 doesn't matter much if how precise it is

33:59 but it would probably be better if it's

34:01 more precise this is almonds don't know

34:12 what just I got all I'll have to say

34:15 what's the difference

34:24 more precise and orders of magnitude

34:33 okay yeah so it's probably good practice

34:36 to just use performance and now for

34:38 these things

34:39 Oh nobody has time to wait this long do

34:43 we see a slowdown mm already oh this is

34:47 already quite not quite slow but little

34:51 slow let's try ten thousand okay it

35:08 doesn't takes too long for my taste

35:11 let's do five thousand binary search the

35:19 four months is not defined Oh doing it

35:25 half that in noches benchmarking a ton

35:32 of code is helpful especially when you

35:34 go for saving lines of code was a speed

35:36 I was just trying to go for correctness

35:38 and not for speed

35:49 [Music]

35:50 I probably misspelled performance right

35:56 [Music]

36:06 oh I need to require a performance folks

36:11 I guess okay all right come on don't be

36:35 that slow why is it getting so much

36:37 slower between 2,000 and 5,000 are you a

36:42 little bit too impatient one Mississippi

36:51 two Mississippi

36:56 oh okay so he already see a big

37:03 difference the quadratic one still took

37:05 zero seconds rounded where's the cubic

37:08 one took four seconds so if we just go

37:12 up by 500 you see something so big

37:16 improvement from the cubic to the

37:18 quadratic algorithm you to seven seconds

37:23 okay yeah it's really slowing down with

37:26 that cubic complexity okay so we have

37:34 good tests we can even use random errors

37:37 I would say let's let's commit this

37:56 just in case and what I want to do now

38:00 is so we have cubic we have quadratic

38:05 let's go for linear right right all

38:10 right so how can we solve this in linear

38:12 time with the quadratic approach we

38:16 looked at every element and then we

38:19 iterated to the left and to the right

38:21 for each element to find the next

38:24 minimum on the left and on the right

38:27 that seems like a lot of duplication

38:29 because we always would iterate over the

38:31 same elements like for this one here to

38:36 find the minimum on the left you repeat

38:38 the steps that this one did you find a

38:40 minimum on the left for this last parts

38:43 more obvious so this one here did one

38:45 two three steps to find this minimum and

38:47 then this one here honor the minimum is

38:49 is right there but you could see how so

38:54 if we do two one five six two and then

39:00 just have a bunch of twos here you could

39:02 see how the effort for all of those

39:04 finding this minimum seems like we're

39:08 repeating the same problem especially if

39:13 you have like three four seven eight

39:20 I'm so proud of my little tool here to

39:22 visualize everything like taking

39:27 iterating over all the bars and going

39:29 single steps to find the minimum it's

39:31 very repetitive and that's exactly where

39:35 we can find some extra time and I want

39:41 to look at this as an extra problem

39:44 first before we can combine it hi

39:47 deceiving how's it going oh I could I

39:50 guess I could push my code so you have

39:52 what we're working on right now okay so

39:57 instead of finding the minimum all the

39:59 time we want to pre-process

40:02 input array and generate two array is a

40:06 left and a right array where we have to

40:08 come in on the left and on the right and

40:15 we can forget for a moment about the

40:19 rectangles and just do that here so

40:21 given an array of integers find the

40:23 nearest smaller number for every element

40:26 such that the smaller element is on the

40:28 left side so Const nearest smaller

40:35 there's a function that takes an array

40:38 and it should return an array so and

40:44 result is this array and now for that I

40:52 equal to 0 I left a that length I plus

40:58 plus so we want to fill this result here

41:05 with the find the nearest smaller number

41:15 for every element such that the smaller

41:17 element is on the left side that it

41:21 makes sense yeah find a newest smaller

41:26 number for every elements of should the

41:28 smaller element is on the left okay so

41:30 how do we go about this so for this one

41:33 here there's nothing on the left side so

41:37 the smallest number we were just return

41:39 minus 1 I guess now for this one again

41:42 there's nothing smallest we would have

41:44 to return minus 1 let's go back to our

41:48 default array here now for this one here

41:51 the smaller number of course is 1 for

41:54 this one smaller numbers for and for

41:56 this the smaller number is also wand

42:04 now a neat trick you might have noticed

42:07 is that as soon as we calculate the

42:10 smaller number for this this bar here we

42:13 will never ever need these large bars

42:17 again when we're computing smaller

42:19 numbers for anything coming on the right

42:21 because why is that the case well

42:23 anything that's smaller than four will

42:26 certainly not have things that are

42:28 bigger than four as the smallest number

42:30 and anything that's bigger than the bar

42:32 at four will stop at the latest on this

42:36 one year so since we can ignore certain

42:40 bars once we've processed them

42:42 we'll use a stack to keep track of the

42:45 bars that we're using hi any nerve hello

42:50 to Austria thanks for joining

42:55 so we need a stack here and I've stacked

43:01 at length is not zero and we want to pop

43:10 things from the snack as long as they

43:12 are bigger than the height that we

43:13 currently have

43:15 so that's right a pop function I guess

43:20 stack that sorry a peak function is a

43:25 function that returns

43:27 [Music]

43:29 thanks for the follower in read of

43:33 what's happening in Austria as to

43:35 whether there do you still have a ton of

43:37 snow

43:38 forgot I said the snow melted and we

43:44 have a he's in Germany now you want to

43:50 return the last of am and stacked at

43:54 length minus one stack

44:05 peak if this is bigger or equal to the

44:10 current element and we're popping okay

44:17 and now I've stacked at length is equal

44:20 to zero that means just nothing on the

44:24 left almost now again next week eleven

44:29 degrees Celsius I wish it with this one

44:31 we are back to like zero and it's super

44:34 windy here if something's on here

44:47 resulted push stack that all right so 4

44:58 2 1 5 6 2 3 console all that log and I

45:09 call this nearest smaller off this array

45:15 oh that looks wrong okay but what do we

45:20 expect to this so for the two we expect

45:22 a -1 I'm just gonna write this here for

45:26 the one we expect a minus 1 and then we

45:28 expect a 1 a 5 a 1 a 2 third right

45:37 smallest numbers smallest one it's one

45:46 for now 5 and then for this one here

45:51 next smallest one is a 1 and a 2

45:55 ok so that's what we'd like to have it's

45:59 not quite what we're getting we're

46:00 always getting a minus 1

46:03 here's our stack years always very empty

46:06 so stacked up push minus 1 minus 1 1 5 1

46:14 2

46:15 all right so does that kind of make

46:17 sense so we're going through this array

46:28 and for every one we want to find the

46:31 nearest left neighbor we go through the

46:35 array once and we're building a stack

46:43 and since the stack has a most n

46:48 elements and we're pushing and pulling

46:50 from it but not more than pushing n

46:52 elements in total because we just push

46:55 once for every element here this is

46:57 definitely linear time so we can find

47:00 the nearest smaller on the left in

47:02 linear time and now that we have this

47:07 result we can use it in or we can use

47:13 the same strategy in this algorithm yeah

47:18 so here we were going through every bar

47:21 that makes sense

47:23 taking the height and then we were

47:25 computing left and right by iterating

47:28 over all the boss again so instead of

47:30 doing that we want to use a stack now so

47:35 we use a function similar to this one um

47:38 one problem with this one is it gives us

47:40 the numbers directly the height of the

47:43 bars it doesn't give us the indices so

47:46 let's change this to give us the indices

47:50 what should that be so you want the

47:53 indices and we always need to so we are

47:55 pushing just the index here and that

48:01 means we need to compare a of this index

48:05 and the same here when we're pushing oh

48:11 no we want to push the index into the

48:14 result right we're comparing height of

48:22 the index and we are pushing the

48:25 the result so let's make sure we get the

48:30 right and this is here so we get minus 1

48:33 minus 1 this one is index 1 now this one

48:37 should have index 2 and then the 4

48:41 should have index 1 and the 5 should

48:44 have index 4 minus 1 minus 1 1 2 1 4

48:51 minus 1 minus 1 1 2 1 4 wait that is oh

49:04 this is 1 to 1 for yes 1 2 1 4

49:12 that's what we want to see here okay oh

49:14 so this function that gives us the

49:17 nearest smaller on the left works so

49:21 let's copy and paste this and make our

49:27 linear function alright

49:32 so instead of credit ik we want Linnea

49:36 hopefully it's really off and at the end

49:38 so we keep track of a max area and now

49:42 we also need Const left nearest which is

49:49 nearest smaller of a and we need a

49:52 constant right nearest okay how are we

49:56 getting the right one obviously we could

50:01 rewrite this whole function and reverse

50:03 everything or we could just use nearest

50:07 smaller of 8 can I reverse an array like

50:12 this

50:20 yes okay hey that rebus okay so that

50:23 should give us the nearest one but from

50:26 the right and then we have to reverse

50:33 all of that again um actually I think I

50:39 want to see that printed out for our

50:42 example okay so we take the height for

50:47 each one and now left instead of doing

50:52 this whole loop here we can just say

50:55 well the left one is left nearest of I

51:00 and the right one is right nearest of I

51:07 and we need to check if these numbers

51:13 are correct the next nearest one was one

51:16 too far on the left okay this should

51:18 still all be correct all right so

51:21 largest rectangle Linea off our example

51:28 here yeah need to print the whole thing

51:36 console that lock that did not go well

51:41 all right so let's print out what we

51:45 have console.log left nearest yep oh

51:54 this one needs another rebus and for

51:58 some reason the area is 12 so that's not

52:00 quite what we want because it should

52:04 still be 10 right doesn't magically get

52:08 bigger

52:09 okay console.log right nearest let's

52:14 have a look at the right nearest one so

52:17 what's the next smaller one for this one

52:20 should be in next one and then for this

52:26 one it should be six and four two it

52:31 should be

52:32 for three it should also be four for

52:36 four again it should be six and four

52:38 five it should be six okay so this is

52:45 what I would like to see why does this

52:47 reversing not work the way I wanted to

52:50 work so we reverse the array and we find

52:57 nearest smaller I see because I should

53:09 be manually do the reverse well not

53:16 manually cancel that log nearest small

53:20 oil a tad reverse I can copy and paste

53:30 three two six five one two all right so

53:37 this is what the array looks like if we

53:40 reverse it and now to the left so we

53:44 have minus one minus one I mean that

53:51 should also work if we do the - once

53:53 here so if we do nearest smaller of

54:01 eight reverse its this and now the

54:07 problem is how do I go from these

54:09 numbers again then we are reversing it

54:16 which was this in reverse order

54:28 shouldn't the left work just like to

54:30 write but we reverse it now we need to

54:34 flip the indices though how do we flip

54:39 the indices

54:45 so we're reversing this okay do we have

55:11 to all right so the -1 should really be

55:19 the 6th a 0 should be the 5 like the

55:23 indices here we're all off how we flip

55:28 the indices hey Mara how's it going so

55:35 we are looking at this problem given a

55:38 non-negative integers representing the

55:40 history behind with the which of its

55:42 bars 1 rent the area of the largest

55:44 rectangle in the histogram we just solve

55:47 this in cubic time in quadratic time and

55:49 now we're working on the linear time did

55:52 you linear time and for the linear time

55:57 I'm using this smallest nearest smaller

56:03 function that's pre-processing my input

56:06 and it's generating this left nearest so

56:12 that works and now I thought I could be

56:14 clever and get the right nearest there

56:16 just reversing the array running left

56:18 nearest and then reversing the result

56:20 but since I'm returning the indices my

56:24 results not quite what I wanted to be

56:27 because now the indices are also

56:29 reversed and I'm not 100% sure how I'm

56:33 reversing the indices because it's not

56:36 just addition to them but do we need to

56:43 have like a map of indices or should we

56:46 just rewrite this function to be like

56:49 left and right nearest smaller left I

56:56 guess that's what we have to do and then

56:58 we can skip all this reversing yeah yeah

57:09 otherwise we would need a map and that's

57:11 like we wouldn't need a map that maps to

57:14 previous and next to the old index and I

57:17 don't want to do that and doesn't seem

57:20 space sensitive so we're just doing this

57:26 here

57:27 right so we going through from the end Y

57:40 is bigger or equal to 0 and subtracting

57:45 I while the stack is not 0 and stack the

57:51 pink is bigger with popping that all

57:56 still looks correct let's just run this

58:05 so if we do this initial rate nearest

58:11 one from the right what are we getting

58:14 we get one 6-4 4-6 6-1 6-4 4-6 six and

58:33 we don't want to push minus one we want

58:35 to push 8 at length six six four four

58:41 six one six six four four okay we're not

58:44 quite there yet

58:48 why would the first one be a six oh

58:55 nevermind I'm going through those in the

58:57 wrong direction results previous one 6-4

59:06 4-6 6-1 6-4 4-6 six days we have the

59:21 nearest to the right and we get the

59:32 right result okay Oh

59:36 however burly how's it going I'm using

59:41 this pretty neat plugin called waka waka

59:45 Jas and that shows me everything right

59:48 here so I don't have to switch over to

59:50 the console all the time um the only

59:53 thing that's a little bit annoying is I

59:54 can't copy and paste and thinks that

59:56 it's showing here but other than that

59:58 it's all good okay so it worked in our

00:02 chest case and let's think about this

00:08 complexity it again so nearest smaller

00:10 left and right they are in linear

00:13 complexity and then we stepping through

00:16 here linearly again so we basically have

00:20 like three times linear which of course

00:23 is just when you okay I am excited to

00:27 see how much faster this is and how far

00:30 we can get

00:31 so when we ran this one here with 3000

00:36 we had to wait four or five seconds yeah

00:42 you can see Coco's working now because

00:44 there's no dots here um might be that we

00:48 have to switch to the console for that

00:51 so if we do note

00:53 maximum rectangle for the 3000 element

00:56 that should take around four seconds for

00:59 the qubit one

01:03 yeah

01:04 zero in five seconds so now I want to

01:06 see how that goes with the linear one so

01:12 with the test function test here so

01:16 instead of this cubic one I want largest

01:23 rectangle

01:24 Linnea let's push all these tests to the

01:38 end

01:54 can see this random error function we

01:57 don't need to look at that and then this

02:01 is the test function kind of don't

02:05 really need these oh yes sir the nice

02:07 thing is if we do the linear cases yeah

02:12 let's run this formula just to make sure

02:23 we do this fill in yeah yep the answers

02:26 are correct and now it's just as linear

02:28 if N is a thousand we'll only need a

02:34 thousand steps which is much better than

02:37 a million or a billion here cool okay so

02:41 it's correct for the small ones a test

02:45 function here takes quadratic and then

02:48 linear and it prints those out and they

02:54 all take zero seconds

02:56 so let's challenge this a little bit

03:00 10,000 should still be zero okay yeah

03:08 and remember how we couldn't even run it

03:10 for like five thousand but the cubic one

03:13 because it was so much smaller okay this

03:15 is starting to take a little bit of time

03:19 exciting let's see how long this takes

03:31 yeah so this is why the interview is or

03:34 like why in general in computer science

03:36 the concept of asymptotic complexity is

03:39 so important you like when you implement

03:43 a indicator how's it going who are you

03:47 joining us from when you implement a

03:51 solution in a quadratic with quadratic

03:55 complexity and one with linear

03:56 complexity just by using a few different

03:59 inputs you can actually see what a

04:01 difference of me

04:02 this one seems to take too long so let's

04:05 take half of it Oh from Britain nice so

04:15 it's already Saturday evening doing

04:17 pretty well and a little bump that's so

04:20 cold outside again but I'm gonna stay

04:23 inside where it's nice and warm you know

04:29 too many years that way it's so slow

04:34 okay so once I was one year is fine I

04:38 can't even beat it 1 2 3 so 1 million so

04:41 we go up to 1.5 million and then we have

04:47 to wait for it

04:49 hi Stan Stan Shunpike thanks for the

04:53 follow ok so that's already took 2

04:55 seconds now let's go up to 2 million

05:09 yeah so obviously you can really stretch

05:14 the two and a half or probably take like

05:16 8 seconds now so with the linear part 6

05:24 seconds we can really compute run this

05:28 algorithm for much larger inputs last

05:38 few years on the way

05:40 okay cool I like this okay yeah eight

05:47 seconds versus the other one still just

05:49 took a fraction a few milliseconds less

05:52 than one second I'm rounding here so it

05:54 looks a bit weird a bit oh all right

05:59 yeah so that was the largest rectangle

06:03 that you can fit under a bar graph the

06:10 program explicitly specifies that it

06:13 needs to be integers but all of those

06:15 should work just fine if you use

06:17 decimals here in fact we can't do that

06:23 we don't need this long one but if we do

06:26 to the two 5:37 I think the test still

06:31 passes we don't get an error thrown

06:33 otherwise my test for throw an error and

06:35 we could also try this one here if we

06:39 had five point three and six point seven

06:42 yep but we expect a ten point six here

06:51 different number I guess because we can

06:54 do yeah that's that's just printed so we

07:01 decided about a little graphic here

07:03 so here the highest one we fit between

07:06 two and three would be five three ten

07:09 point six but here we get three times

07:12 for like almost three times four which

07:14 is almost twelve so that's why it gets

07:17 bigger as we increase this one I take

07:20 this down yet then it's still between

07:23 these two okay and you could even make

07:30 this work for negative numbers wait

07:36 could you make it work for negative

07:37 numbers let's draw something negative

07:42 here oh so negative

07:47 I guess you would have to pre-process

07:49 the array and split it up into chunks

07:52 because whenever you have this kind of

07:54 crossover you can't fit a rectangle so

07:57 you would have to split it into chunks

08:00 and then just run the linear algorithm

08:04 on the chunks so here you'd have the

08:06 maximum here yeah okay so the problem

08:11 would be a little different but the

08:12 complicated part about getting a linear

08:15 solution would stay the same we just

08:16 have to pre-process this into smaller

08:18 chunks where they are all positive or

08:19 negative and then just work with the

08:22 absolute value from there all righty

08:26 onto the next problem okay surprisingly

08:30 again we're given a non-negative

08:33 integers Rubin sending an elevation map

08:35 where the width of each bar has one

08:37 compute how much water is able to trap

08:39 after raining so very similar looking

08:42 problem again we have non-negative

08:46 integers and array of them and they

08:48 represent an elevation map and now we

08:51 are supposed to figure out how much

08:52 water is being trapped after raining so

08:55 if we draw this one this is our

08:57 elevation map and one thing we could do

09:03 here is we set this to 100%

09:09 [Music]

09:14 oh I need to impact okay yeah maybe this

09:19 is easier to see what a hundred percent

09:21 instead of two ninety seven percent so

09:25 if it rains where would the water be

09:30 trapped so on the left here what I would

09:32 just flow out I get into the ocean or

09:36 whatever but it wouldn't be trapped here

09:37 but then if it had rained here we would

09:40 have water trapped at index two of hide

09:42 one and then over here there wouldn't be

09:47 any water trap but there would be water

09:49 trapped here between four five and six

09:52 at high - and then there would also be

09:55 some water right here so you would have

09:59 one two three four five six square units

10:04 of water and see yes so that should give

10:11 us 6 units of water so water is a

10:17 function that takes an array and it

10:24 should return the amount of water

10:26 trapped okay so how can we do this this

10:30 looks a lot like the problem we just had

10:32 right we also had these bars and we was

10:35 supposed to like fit something in these

10:37 bars and we came up with a linear

10:41 solution by using stacks how would we do

10:44 this here

10:50 first of all what's in the eve approach

10:55 we could take we could iterate over all

10:58 the bars and for everybody we have to

11:01 figure out what the height of the water

11:03 is there and then so here for example at

11:09 index for the height of the water is -

11:12 can't be higher than - it'll flow out

11:15 after - so we would take 2 minus the

11:18 height of the bar 1 2 minus 1 this one

11:20 water unit trapped here

11:24 we could do that right now how do we

11:26 figure out the height if we add any

11:29 point we would go to the left and find

11:34 the maximum bar and we would go to the

11:37 right and trade the maximum bar and then

11:39 of those two Maxima we would take the

11:41 minimum for the height right so let's

11:44 just usually do that before we do that

11:48 what's the complexity we're iterating

11:50 over all the indices and for every index

11:53 we go all the way to the left and all

11:55 the way to the right so it would be

11:58 quadratic all right

12:01 well I equals zero I less than eight at

12:05 length I plus plus left left

12:15 maximum equal 0 for J equals J Big O

12:32 equals zero Janos to the laughs laughs

12:37 max its mastered max of the previous Max

12:41 and a J and I guess we should start one

12:53 left J right otherwise the maximum would

12:57 be the thing itself well it doesn't

13:00 matter too much and then we also need a

13:04 right maximum so J is wanted right why J

13:12 is less than the length and we're

13:21 updating the right maximum lab height

13:27 equals map men left and right maximum

13:34 and then water plus equals the height

13:44 now let's call this water height minus

13:52 the height at that thing so we're

14:00 calling water on this input and crow

14:10 crow doesn't print anything out because

14:12 I haven't turned it on he's going a new

14:14 father okay oh so many constant variable

14:22 this is just W okay that did not quite

14:28 work out yet let's see what I did wrong

14:39 one two and three one is a maximum sure

14:47 [Music]

14:48 why would it say two and three instead

14:51 of three and seven oh because I'm

14:55 putting into height I don't want to know

15:02 I want to put into height yeah so the

15:04 height is zero one two or three three

15:17 two one all of those it is three for

15:20 these of this two on for this one I'm

15:24 thinking it is one but it really should

15:26 be zero

15:27 oh yeah one

15:37 okay I see what's going on here so I'm

15:40 taking the water height which I guess

15:48 correct so zero zero but then here I'm

15:53 adding negative numbers to it if the

15:56 height was less than the maximum so

16:00 maybe better if we're starting yep now

16:09 it works okay so the water trapped in

16:16 this array has area six and this

16:22 algorithm here is quadratic because

16:29 we're iterating over every element and

16:32 then again we iterate twice but that

16:36 doesn't matter that's just a constant

16:37 factor but then again reiterate all the

16:39 way left to right okay well at least

16:42 this is correct so how do we get this

16:48 down to linear time

16:51 what's a repetitive part here for every

16:54 bar we're going all the way to the left

16:56 and all the way to the right to find the

16:58 maximum this looks a lot like we could

17:01 pre-process it and do it once and then

17:03 just access it in the last problem we

17:08 were looking at the largest rectangle we

17:10 were using a stack in a smart way so we

17:14 could get this pre-process of the next

17:17 nearest smaller one and then your time

17:19 but this one's actually easier and if

17:22 you try to do it with a stack I think it

17:24 gets very confusing like there is a way

17:26 to solve this with stacks but it's not

17:28 really how I think about this when

17:31 you're using stacks you're kind of

17:33 looking at levels of waters and you like

17:36 figure out oh there's like one here and

17:38 then there's three here and it's it's

17:42 just I know I think it's more complex

17:46 hi famous sick bro how's it going and

17:53 also hello girls and non girls so guys

17:57 hello everybody I guess

17:59 oh yeah we are doing very we're doing a

18:04 common interview questions that's the

18:06 whole point of it we want to do the

18:08 common ones most interview questions

18:11 like there's a few tricks or concepts

18:15 and then any interview question is just

18:18 a variation of that like it's either a

18:20 cute little story like water or it's

18:24 some sort of variation but it's always

18:26 similar tricks that's like

18:28 pre-processing so you have something in

18:29 linear time use a stack use a queue you

18:33 use a hash set at the data structure use

18:36 sub sums for something so once you see

18:42 in a bunch of these tricks or concepts

18:45 you're hopefully able to when you get to

18:49 the interview recognize what kind of

18:51 concept will solve it yeah I'm sorry

18:54 little doggie is barking but now he's

18:57 sleeping again he's a pretty good dog

19:00 hair to say he's very good alright so

19:03 how do we find this array of maximums to

19:08 the left and to the right I think it's

19:11 pretty easy and I want to say the array

19:13 is just that thing here that we already

19:16 got printed so let's just write a

19:20 function for that so Const left max as a

19:32 function oh yeah he wanted to say hi to

19:35 you he's a shy doctor he's not really

19:39 good at Twitter star so he doesn't want

19:41 to come on the show I guess yeah I guess

19:46 he heard the hi guys and he just wanted

19:48 to say hi back

19:51 hey big one yes we did finish the

19:53 maximum rectangle um we did it in cubic

19:56 time quadratic time and in the end we

19:58 did it in linear

19:59 I'm using a stack to get this array of

20:04 left and right nearest like the index of

20:08 the nearest smaller on the left and now

20:10 we're doing a very similar problem but

20:12 with a different solution similar in the

20:16 sense that we are using both times just

20:18 like a histogram graph here yeah but you

20:22 can always rewatch it alright so how are

20:25 we getting this array of left max so we

20:35 want to return an array here and I guess

20:38 not surprisingly we iterate over a so I

20:46 could 0 I less than a that length I plus

20:50 plus so for every element is it easier

20:57 if we start with the brightest maximum

21:00 no it's not so what's the maximum on the

21:06 left for the first one the maximum is

21:11 zero and then for the next one the

21:18 maximum is itself and then okay M of I

21:30 is equal to method max of maximum and a

21:36 of I that's what's happening console

21:47 that large

21:53 oh and okay I got it

22:03 I don't need a maximum I can just always

22:08 use the last one so MRI is a of I minus

22:16 one M of I minus one so the maximum is

22:37 zero

22:38 now I take max of I is the maximum of

22:43 zero or one so it should be one and now

22:48 I'm taking the Mac why does this not

22:52 work

22:53 oh that's a silly okay do one one two

23:02 two two yep

23:04 okay that looks good now how do we do

23:07 this for the right do we need just like

23:11 before do we need a function that goes

23:13 through in the other direction or could

23:15 we reverse the array so if we reverse

23:21 the array I think we could just reverse

23:23 the array all right so let left max is

23:33 equal to left max of a right is equal to

23:44 max of a that reboots and then for

23:51 everyone instead of this other full loop

23:53 here

23:57 I can just take left of I and I actually

24:07 want to call those left's and rights she

24:11 says more than one in them in the array

24:22 okay it's not quite right yet because I

24:25 think what I did here is so I'm

24:27 reversing the array I'm finding the max

24:31 but then I have to reduce it back right

24:37 no no we lost the water shoot okay well

24:43 before we play with the reverse let's

24:46 make the right max so I is equal to

24:53 eight at length - - while I is bigger

25:00 than zero and we want to go smaller here

25:05 and here we have the one that's one

25:07 bigger the one that's on the right

25:21 and that's print right max okay that

25:29 don't work because we need to initialize

25:33 this differently so maximum of max that

25:36 length minus one last one he is equal to

25:41 zero and then we let I start one smaller

25:47 than the last one and we setting it okay

25:56 what is wrong here maximum is an array

25:59 and we set the last one which is a dot

26:05 length minus one so we go to 3 3 3 2 2

26:10 to 0 does that look right the maximum on

26:22 the right is 3 and if it was it's too

26:26 good for this one it's 0 ok or should

26:35 the last one B of 1 yes the last one

26:41 should be a 1 so it should be a of a

26:47 that length minus 1 whereas this one

26:50 should be a 0

26:53 yep and now it's 6 okay I needed these

26:57 numbers here because when I'm

27:01 calculating the water height that I'm

27:05 adding otherwise I would have as a

27:09 negative number

27:10 yeah okay all right so instead of using

27:21 just right max now that everything is

27:24 correct

27:25 let's do left max

27:28 but reverse this and then reverse it

27:35 back okay

27:36 yeah this seems to work why does this

27:42 still say square that's just our hand

27:48 okay so to me personally I guess to trap

27:53 water looks just as hard as the maximum

27:57 rectangle because this one is equally

27:59 hard and then it's hard to figure out

28:02 where the water stops but then when you

28:04 think about it a little more it's

28:06 actually somewhat more linear because

28:10 you just need to find the maximum on the

28:12 left and on the right for the histograms

28:15 you didn't need to find the maximum

28:16 which would stay the same no matter how

28:21 far you moved unless you moved over that

28:23 edge for the histogram you had to find

28:25 the next smallest one which I thought is

28:28 a little harder and that's also why the

28:31 history gram you can't solve it in this

28:34 linear without like without a stack it's

28:37 easy to solve in a linear fashion with a

28:39 stack with this one you don't need

28:41 something as complicated as a stack you

28:44 just go through this here very basically

28:46 and find this pre-process this array

28:49 that gives you the maximum Zhan the left

28:50 it's just keeping track of the Maxima

28:53 you saw and only get bigger and then

28:58 doing that first it's easy to find a

29:01 linear solution here okay yeah

29:06 unfortunately I don't have a ton of time

29:08 today a bunch of errands to run so I

29:11 think 90 minute stream is good here what

29:17 did we change okay we just commented

29:26 that'll be put decimals and so let's

29:35 Oana trapped and yeah solution for trap

29:43 lot of problem and - the other ones all

29:51 right

29:56 hi there'll be one nope I don't feel

30:02 like doing this with no extra space so

30:07 it's a good question though I guess

30:09 that's like homework for everybody yes

30:13 unfortunately I have to leave but if you

30:17 wanna if you paid attention here

30:19 we had to allocate this left's and

30:22 rights array so we needed extra space

30:24 and we can actually get away without

30:27 doing that um if you want to try it I

30:31 would think about like moving to

30:34 pointers in from left and right that's

30:36 probably the most helpful all right

30:39 or maybe build one wants to solve it on

30:43 streem and you can watch them okay

30:48 alright thanks everybody thanks so much

30:51 for joining me I hope you have a great

30:54 rest of the weekend

30:56 unfortunately next Saturday I'm

30:58 traveling so no stream on Saturday but

31:01 we have a bonus stream coming up on the

31:06 19th I know I'm gonna be seeing myself

31:11 and I'm gonna see advertisement okay so

31:14 I'm the under 19th year

31:17 I'm cording together with why is this

31:22 crystal it's together with Andy coding

31:24 together with Andy he's an engineering

31:30 lead for the go team at Google and we'll

31:33 do go for JavaScript developers because

31:36 I don't JavaScript developer and he'll

31:38 show me what to do so that's on Tuesday

31:41 the 19th tune and for that I won't be

31:43 here next Saturday but in two weeks

31:45 again

31:46 all right thanks so much everybody I

31:49 hope you had fun oh and if you were

31:51 wondering I was using glitch to quickly

31:53 make this cool thing so I could see my

31:55 histograms it's Google charts and then

31:58 I'm just using glitch we don't have to

31:59 worry about where do I host it how do I

32:01 run it it's all here and the

32:04 coordinating glitches you can go to any

32:07 project and remix it so well it's kind

32:11 of like a git clone except that it's up

32:13 and running right away so if you want to

32:15 make this a little more beautiful if you

32:17 want to add the water to it that would

32:19 be a good one

32:20 go do it if you did send the link to me

32:24 on Twitter I'd love to see it

32:26 alright thanks everybody hope to see you

32:29 Tuesday in a week have a great weekend

32:31 bye bye

## Leave a Reply