Episode 05 comes hot with histograms, rectangles, stacks, JavaScript, and a sprinkling of adult themes and language. Brace yourselves! Full text-form code is available here: jg.gg/largest-rectangle-in-a-h...
Пікірлер: 313
@brandonm10887 жыл бұрын
I was amazed for the longest time on how you write so well mirror until I figured you most likely are not left handed. Really clever presentation!
@Jeff.Wilson3 жыл бұрын
It's very hard to come up with the optimal algorithm when you hear this problem for the first time on your interview. People who are giving this question on the interview and expect to get an optimal solution, shouldn't be performing interviews at all.
@HughGuiney7 жыл бұрын
DID ANYONE ELSE NOTICE THE INDIVIDUAL CHARACTERS FALLING DOWN FROM THE BOARD AFTER HE SPRAYED IT AT THE END??? 15:52
@pspsora7 жыл бұрын
i need a t-shirt that says "function popThatShit(){}"
@Shaddymaze4 жыл бұрын
High quality all around. Well done, sir! You just earned yourself a sub.
@manusharma58173 жыл бұрын
probably the best explanation on KZbin even today. Thanks, man.
@arjunkashyap88963 жыл бұрын
6 seconds into video: "Wait am I watching a coding interview tutorial ?!?!" Data Structures and Algos are such complex and mind numbing topics. I love the fact that you added humor to such complicated topics. Its good to be laughing while learning. It just made learning a lot more enjoyable. SUBSCRIBED
@thequantartist4 жыл бұрын
Just discovered, this channel. Simply love it!
@albertoesquivias60737 жыл бұрын
just found your channel, its awesome! keep being yourself and hopefully you upload more soon. thanks!
@crankyinmv3 жыл бұрын
Thanks for this. I love seeing a solution in JS. I managed to do this problem using a tortured DP-ish solution which kept track of rectangle areas and heights. Nice to know there's a sane solution.
@MaxHeckelIsMe8 жыл бұрын
Great video, going to binge watch the rest now.
@pradeepravi75917 жыл бұрын
Dude ..thank you so much... I completed this problem ... :-p < Your Largest Rectangle submission got 50.00 points. >
@aditya0707916 жыл бұрын
Loved the video ! Infinitely more interesting than other ones out there.
@chicken61807 жыл бұрын
"Uncut Jackson... unrelated to my parents decision"... SO subtle but i had to listen again to see if that was what I thought it was
@sajanchoudhary1085 жыл бұрын
Finally, someone has succeeded in explaining this question.
@vanjajaja14 жыл бұрын
“i, like most people who work in java, dont know java.” i can relate.
@programminginterviewprep18087 жыл бұрын
I am wondering how did you take this video? It looks very interesting!
@justingivens2178 жыл бұрын
Awesome explanation of problem and solution! Keep them coming!!
@HardCapGamingOfficial7 жыл бұрын
I laughed so hard when he named the function popThatShit xD
@snejati868 жыл бұрын
Make some promises and you might get your callbacks .... I'm sad about this joke.
@jackson-gabbard8 жыл бұрын
That's not a joke I made is it? I agree that it's awful.
@stasvpavlov7 жыл бұрын
Sina Nejati I can tell that you are probably a really l "fun" guy.
@bhaumin6 жыл бұрын
I await'ed at a sink
@iveted47383 жыл бұрын
@@jackson-gabbard dude why'd you stop making these videos?
@MrNargleflex7 жыл бұрын
Hey this video rocks! I had been puzzling for a while on how to do this, and the best I could do while getting a correct answer was O(n^2) time complexity, which is garbo. Thanks for the great explanation!
@DarcMagikian Жыл бұрын
Is this not also O(n^2)? since there's a while loop inside a for loop?
@asdfghjklqwertyuiop78997 жыл бұрын
love your style. pls keep making more.
@ranzort4 жыл бұрын
All your vids are so good I have learned to tolerate bad BGM
@StockDC27 жыл бұрын
Hey, thanks for the video. I have a quick question if you don't mind. When you went from 3 to 2, you only popped the top value from the height stack (since the rectangle at index 2 started from index 1). However, when you go from 2 to 1, you pop from both stacks. Can you explain why? From my understanding, there is still a rectangle from index 1 to index 3 with height 1. So what I have in the Position and Height stack when i = 5 is: P - H 4 - 2 1 - 1 0 - 1 Thanks!
@Milkyboy928 жыл бұрын
Cool video! As a general idea for avoiding popping that shit at the end, you could insert a 0 at the end of the histogram. Or is this too hacky?
@DiogoNeves7 жыл бұрын
That's interesting! I'd guess explicitly popping is more... explicit and clear. Can't wait for more opinions/logic on this :)
@ExtinityOfficial7 жыл бұрын
Just got a something new in an interview i haven't seen before. Find the amount of magic squares in a given rectangle 2d array. Took me a while to figure out the optimal way to do it
@g00dvibes477 жыл бұрын
"...getting a little bit bored with the polite, PC...." subscribed.
Your solution is correct, but the magical change at 15:45 is suboptimal - it can lead to having multiple entries for the same height at the top of your stack. For example input [1,2,1] leads to having [0,1] and [1,1] in your stacks at the end of the for loop. A better solution would be to add "|| h > hStack[hStack.length - 1]" to the if statement you removed. Just wanted to chime in since I just went through all your Coding Interview Problem videos while preparing for my coding interview. They were a great resource, thanks for all the effort you put into those!
@itizir7 жыл бұрын
Was going to make a similar remark... In fact it looks like it would even potentially give wrong answers! Take [ 1, 2, 3, 2, 1 ]: the largest rectangle is 2x3 = 6, but with the given code, the two 2s would be counted as part of separate rectangles in the stack (of size 2x1 and 2x2), so the code would think the 1x5 rectangle is bigger. Eh. Or is it me who's missing something? :P
@itizir7 жыл бұрын
Ah no indeed, I'm the one who missed something: the size is calculated keeping the very last index accessed, so it will indeed see the correct rectangle... My bad!
@sirnawaz6 жыл бұрын
@Sebastian: Wow.. I was thinking exactly the same thing.. and in fact, I corrected this part: repl.it/repls/WoefulFavorableCustomer And then I started looking for a comment, hoping that someone else (apart from me) would pointed out this.. and I found yours. Thanks for confirming that WE are right.
@sgtoverload_51675 жыл бұрын
awesome stuff man, keep up the good work i really like your thinking style..
@EvanKozliner4 жыл бұрын
This question is wild. Awesome explanation :)
@lachlanhillman74694 жыл бұрын
You don't need the heights stack. Just modify the original heights array with the new reduced height values.
@motocomputer3 жыл бұрын
this is such an amazing explanation
@TheTwilightHero8 жыл бұрын
Really loved it!
@subham-raj4 жыл бұрын
*We can do this with only single stack too*
@kristymayo4946 жыл бұрын
I'm super jealous of your markers. I need blood markers in my life.
@TheJohn68667 жыл бұрын
Could you please explain the case when there is just 1 bar at position 0? I think the maxarea should be 1 but your code would return 0 since pos and tempPos would both be 0.
@MrDemianTV7 жыл бұрын
They say you can grab a person's attention in the first 15 seconds of the video. You nailed it.
@bob844097 жыл бұрын
Great job on the video, thank you for making this!
@michaelcoppinger7868 жыл бұрын
Really great vid! Like how you keep the problems interesting and offer entertaining and clear explanations. Enjoy your work a lot :)
@dubeya018 жыл бұрын
Very well articulated! Keep it up
@sdddyr8 жыл бұрын
Awesome video, tried it in C# and works nice !
@sureshchaudhari44654 ай бұрын
Jason Stathum from action hero to Software engineering he learned everything huge respect :P
@deepaligarg76432 жыл бұрын
Very nice. The code works. Thank you so much for making this video and explaining it so very well.
@naythaniel7 жыл бұрын
+Jackson Gabbard, JavaScript has Maps and Sets now (and WeakMaps and WeakSets), so not just 2 anymore. Although probably you knew that already.
@bennettbmadavana7176 Жыл бұрын
Thank you so much was stuck on this problem for days, finally clicked ✨
@bokonon887 жыл бұрын
after processing index 3, how is the 1x(4-1) rectangle of height 1 starting at position 1 ignored?
@Bdjdiwhbkdk7 жыл бұрын
I have a question. This is obviously a coding interview problem, so you need to code the thing. But what if using stacks isn't the "obvious" method, and just talking your way through and using stacks is confusing to the interviewer? You'd obviously want your interviewer to agree that your code works right then and there. You're not really gonna debug it and test if it works. So you might want to draw those stack diagrams and the histogram. But should you be doing this? When you're coding, is it okay to draw pictures to visualize your thought? And also, rather, SHOULD you be visualizing your thoughts during a coding interview?
@jackson-gabbard7 жыл бұрын
In the interviews I've done, candidates who could draw a coherent visual to help them make sense of the problem tended also to write better code and explain their code better. If you can draw a visual quickly that puts you and the interviewer on the same page, I think that's definitely to your advantage. However, it's a matter of timing. If you spend 10 minutes diagramming, you're probably taking too long. 2 or 3 minutes, tops. Then focus on the code. Also, you totally should be debugging and testing mentally once you finish the code. Good question.
@revantnayar34086 жыл бұрын
Jee B to
@TheSexGod4 жыл бұрын
amazing explanation. do more videos like this!
@RaviKumar-vk6ib4 жыл бұрын
It was awesome experience...didn't get bored for a sec...please keep up this swag!!!
@Anonymous-ql7gn7 жыл бұрын
Simly Best tech video I ever seen.
@spiffmonkey17 жыл бұрын
Not the most clear explanation (which might be a good thing) but makes people like us have to think and understand more about how it works.
@Lashovadjs7 жыл бұрын
Really some clever tricks, interesting.
@SephirothITM7 жыл бұрын
Did you leave it to dry for a while before you cleaned it at the end? The letters don't drip, but they move in tact... weird effect.
@reyou75 жыл бұрын
That's how I do interviews, walk in the room and say "hey, what's up motherfuckers?"
@arijiang79963 жыл бұрын
Really clear explanation with beautiful visuals (did you actually write in reverse???), I just find the bg music a bit distracting but other than that true awesome!
@ApurvJaiz3 жыл бұрын
I guess it would be a lot easier to just flip the video while editing.
@soumya52007 жыл бұрын
How did you create a video that makes you look like you are writing on glass?
@TheJayRap7 жыл бұрын
wow this guy is so smart at cursing
@ravinder0901917 жыл бұрын
Colol explanation. Thanks. Please come up with a video on Dynamic Programming. Thanks.
@TimothyLeeBanks6 жыл бұрын
man started the vid with "what up mothafuckas" LMFAO
@user-sl5vw4vi6s4 ай бұрын
It is a shame you don't make videos like these anymore. You are much more didactic than the tops G's on youtube on this topic.
@BigWetTits17 жыл бұрын
Another interesting task (was on the twitter interview): Count the amount of water after rain that will stay between Histogramm pillars. So in Histogramm 2, 3, 2, 4, 1 there's gonna be 1 water above 2 between 3 and 4.
@ciphertester11476 жыл бұрын
Jackson Gabbard, I can't seem to follow how you got the starting position for the 3rd bar with height 2, for example if you took away the first bar and you just have an array of histogram heights of 3,2,1 how would you know that starting point of say height 2 or height 1. I think you need to hold these values. I would create a hash map which has height as the key and increment it each of the key by one if it qualifies/valid or pop it and compare it to the max value. A good test case to consider is 3,3,3,2,1,2,4,4,3,3,2,0,3,3,3,2,2,1,1,1,1,1
@satang5004 жыл бұрын
Hi Jackson, your two stack approach is much easier to compute area. When I first see this problem, I thought about stack and keep adding as long as me is larger than top of stack while content of stack is larger me, keep popping. But what I stuck was in your example, when index is 3 with values [1,3,2,1], I thought I have to compute all possible rectangles such that [1]=1, [2,1]=2, [3,2,1]=3, [1,3,2,1]=4, but no videos explain why I don't have to compute the rectangle between two indices [0, 3] and instead they just compute [1, 3] which means we always guarantee that area between indices [1, 3] always larger than indices [0, 3]. I don't understand how come area between [1, 3] always larger than [0, 3] ?
@parthapratimmallik83547 жыл бұрын
Cool... Loved your presentation...
@brifog697 жыл бұрын
How the fuck did he write those words at the start in reverse so well?
@kunalsinghgusain20706 жыл бұрын
great approach and great explaination i've seen so poor explainations. Yours is better than all others. i have a problem and i wish you could solve it in next videothat is "given a matrix of 0 an 1's how can you find maximum area rectangle?".
@ON-ne1rd5 жыл бұрын
What happens if you replace the tempPos logic with pstack[-1]+1 when stack is not empty and let it be zero when stack is empty? Basically I am thinking the tempPos logic may be redundant. Am I wrong? In what cases does this not work if it doesn't?
@bheshgurung69465 жыл бұрын
The implementation fails for [2, 1, 5, 6, 4, 4, 3]. It does not check if the next height is equal after encountering a smaller height. For the sample, it returns 10 instead of 16.
@tanmayrauthan57404 жыл бұрын
I liked and subscribed after that intro
@j-espresso Жыл бұрын
Well done and thank you Jackson. You made it so intuitive. Java version is here is for critic 🙂 public int findLargestRectangle(int[] heights) { if (heights.length == 0) return 0; int currentPosition = 0, tempPos = Integer.MIN_VALUE, maxArea = Integer.MIN_VALUE; Deque positionStack = new ArrayDeque(); Deque heightStack = new ArrayDeque(); for (currentPosition = 0; currentPosition < heights.length; currentPosition++) { int currentHeight = heights[currentPosition]; if (heightStack.isEmpty() || currentHeight > heightStack.peek()) { positionStack.push(currentPosition); heightStack.push(currentHeight); } else if (currentHeight < heightStack.peek()) { while (!heightStack.isEmpty() && currentHeight < heightStack.peek()) { tempPos = positionStack.pop(); maxArea = Math.max(heightStack.pop() * (currentPosition - tempPos), maxArea); } heightStack.push(currentHeight); positionStack.push(tempPos); } } while (!heightStack.isEmpty()) { tempPos = positionStack.pop(); maxArea = Math.max(heightStack.pop() * (currentPosition - tempPos), maxArea); } return maxArea; }
@delmarfenn70686 жыл бұрын
Would the largest rectangle be in the empty space and not the "stacks"?
@shankardaruga32646 жыл бұрын
The best explanation :)
@arpanpandey78544 жыл бұрын
dude u r hilarious ! keep the good work up !
@victorbizimis94847 жыл бұрын
how are you writting in reverse ?
@vinknut3 жыл бұрын
At 6:06 there's a mistake. The largest rectangle isn't 3, it's 4.
@kevincui16315 жыл бұрын
you don't need the weird sound effect. It messes things up
@lesterdale72767 жыл бұрын
Elegant solution to the problem, but what analysis did you do to come up with this solution or is it that it's a well known problem with an equally well known solution. My thinking is are people coming up with creative solutions to problems based on their own hard work and ingenuity or is it just an exercise in knowing classical problems.
@MichielvanderBlonk Жыл бұрын
I came up with this solution myself. It's on hackerrank in the stacks category, so you already get a hint that you should be using stacks. From there on you find out what you need to retain in order to find the largest area.
@AndrewReisdorph8 жыл бұрын
Now that's a lot of shit popping
@KanagaveluSugumar3 жыл бұрын
Initially i confused that video is not synched with audio and got stuck! But overall it is good effort.
@anolisporcatus4 жыл бұрын
your videos are the bomb.com man! keep it up
@toomasvendelin2 жыл бұрын
A bonus question: is the author/presenter left-handed or right handed? Many thanks for a stellar example on how to make a KZbin video!
@sreekanthjujare3 жыл бұрын
I am curious how he created writing on the glass effect. Any one knows?
@MrGowds7 жыл бұрын
presentation is dope !
@giubueno7 жыл бұрын
Excellent video two thumbs up for it and one down for the code in Javascript because I think it would be more descriptive in Java.
@insights152435 жыл бұрын
Regarding your brute force method, if I got you right then I think you're wrong: take the histogram [9,8]. Your brute force method will return 9 while the right answer is 16. You need to go both right and left (and not only right)
@lipache6 жыл бұрын
Thank you for your help and your vid is nice, but if you could name the stack as "Start Growing Positions" corresponding to the record in the "heights" stack, it would be easier to understand.
@israelmcculley29272 жыл бұрын
If you use a Tuple you can just use 1 stack.
@keepallprivate76167 жыл бұрын
I wonder if it will going to be really a rectangle at the end of the day.. a square maybe?
@souparnomajumder2 жыл бұрын
are you fluently writing form right to left with the characters mirrored !
@samuellee21317 жыл бұрын
Is he like writing backwards
@vineethsai15755 жыл бұрын
Flip the video.
@tienanh20077 жыл бұрын
How does the letters just slide off like that ?
@arpitjangir33492 жыл бұрын
Okay so I played the video and I had to rewind in first 5 seconds
@takanashiouken4 жыл бұрын
Is it only me? No matter how many time I read this still don’t get how does tempH*(pos-tempPos) get the area?
@TomusMedia8 жыл бұрын
I don't understand this, how do you write so good backwards?
@SHUBHAMRAGHUWANSHI_ASKN5 жыл бұрын
missed the case of equals(h === hstack[len-1]). nice video btw.
@bkkhokhani5 жыл бұрын
This case is covered in the code. Try this example with histogram height value [1, 2, 3, 2, 1]. The code will find the correct rectangle area which is 2 * 3 = 6.
@tagadvance7 жыл бұрын
What might this algorithm be used for? What value is there in knowing the area and position of the largest rectangle?
@JacksonGabbard7 жыл бұрын
TaG, there are a million real-world algorithms where this might be useful. For instance, image processing. If you're trying to identify the dominant luminosity range of an image perhaps. In audio processing, you might use a similar approach to determine the primary frequency range in an audio sample. You might also use it in GPS-related calculations, looking for the period of movement within a range of time.
@ruffert1008 жыл бұрын
Great video performance! But from the algorithmic point of view I would suggested this (in pseudo code) maxArea = 0 for all l:listOfConnectedRectangles in listOfListOfConnectedRectangles do currentArea = width(l) * min(height of rectangles in l) maxArea = max( maxArea, currentArea ) end And ah well, yes, I would also need to specify how to derive listOfListOfConnectedRectangles. :) Anyway, this is a suggestion from the top of my hat, what do you think?
@skripnikalexander8 жыл бұрын
In your code the min(height of rectangles in l) will give an incorrect result, as the best area of listOfConnectedRectangles is not the lowestHeight(l)*width(l). E.g. in case of l = [1, 2, 4, 5], the currentArea should 4 * 2 = 8 instead of 1 * 4 = 4
@ruffert1008 жыл бұрын
Need to think about that. Thanks :)
@itizir7 жыл бұрын
Doesn't it depend on how Eduard defines 'listOfConnectedRectangles' and 'height of rectangles in l'? I think he rather meant something like (given your example input): "take the rectangle of width 4 (starting at 1); its height is 1 (the min value), so its area is 4; now take the next rectangle, of width 3; the min is now 2, so the size is 6; etc. etc." In this case it would be correct. The problem is it is very far from optimal: it is just the 'brute force' approach Jackson talks about at the beginning of the video (2:12). Since you potentially loop over all the columns for each and every column, it takes O(N^2), while the stack-based solution presented here is O(N)...
@troycashphotographs3 жыл бұрын
thank you
@tintiniitk3 жыл бұрын
How has he created this visual? It looks like he's writing on a transparent glass and he's on the other side.. but then that'd mean he is writing in a mirrored manner. If he's writing on a mirror, then how is he behind the board?