Coding Interview Problem: Largest Rectangle in a Histogram

แชร์
ฝัง
  • เผยแพร่เมื่อ 28 พ.ย. 2024

ความคิดเห็น • 314

  • @Jeff.Wilson
    @Jeff.Wilson 3 ปีที่แล้ว +16

    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.

  • @HughGuiney
    @HughGuiney 7 ปีที่แล้ว +39

    DID ANYONE ELSE NOTICE THE INDIVIDUAL CHARACTERS FALLING DOWN FROM THE BOARD AFTER HE SPRAYED IT AT THE END??? 15:52

  • @brandonm1088
    @brandonm1088 8 ปีที่แล้ว +13

    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!

  • @pspsora
    @pspsora 8 ปีที่แล้ว +31

    i need a t-shirt that says "function popThatShit(){}"

  • @arjunkashyap8896
    @arjunkashyap8896 4 ปีที่แล้ว +19

    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

  • @chicken6180
    @chicken6180 8 ปีที่แล้ว +1

    "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

  • @sebastiansiatkowski3720
    @sebastiansiatkowski3720 8 ปีที่แล้ว +17

    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!

    • @itizir
      @itizir 8 ปีที่แล้ว

      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

    • @itizir
      @itizir 8 ปีที่แล้ว +1

      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!

    • @sirnawaz
      @sirnawaz 6 ปีที่แล้ว +1

      @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.

  • @snejati86
    @snejati86 8 ปีที่แล้ว +51

    Make some promises and you might get your callbacks .... I'm sad about this joke.

    • @jackson-gabbard
      @jackson-gabbard  8 ปีที่แล้ว +9

      That's not a joke I made is it? I agree that it's awful.

    • @stasvpavlov
      @stasvpavlov 8 ปีที่แล้ว

      Sina Nejati I can tell that you are probably a really l "fun" guy.

    • @bhaumin
      @bhaumin 7 ปีที่แล้ว

      I await'ed at a sink

    • @iveted4738
      @iveted4738 4 ปีที่แล้ว

      @@jackson-gabbard dude why'd you stop making these videos?

  • @naythaniel
    @naythaniel 8 ปีที่แล้ว

    +Jackson Gabbard, JavaScript has Maps and Sets now (and WeakMaps and WeakSets), so not just 2 anymore. Although probably you knew that already.

  • @Virtualexist
    @Virtualexist 4 หลายเดือนก่อน

    This was 8 years ago? Bro was way ahead of his time!

  • @manusharma5817
    @manusharma5817 3 ปีที่แล้ว +1

    probably the best explanation on TH-cam even today. Thanks, man.

  • @lachlanhillman7469
    @lachlanhillman7469 4 ปีที่แล้ว

    You don't need the heights stack. Just modify the original heights array with the new reduced height values.

  • @vanjajaja1
    @vanjajaja1 5 ปีที่แล้ว +7

    “i, like most people who work in java, dont know java.” i can relate.

  • @bheshgurung6946
    @bheshgurung6946 5 ปีที่แล้ว

    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.

  • @arpitjangir3349
    @arpitjangir3349 2 ปีที่แล้ว +1

    Okay so I played the video and I had to rewind in first 5 seconds

  • @ExtinityOfficial
    @ExtinityOfficial 7 ปีที่แล้ว

    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

  • @j-espresso
    @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;
    }

  • @insights15243
    @insights15243 5 ปีที่แล้ว

    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)

  • @toomasvendelin
    @toomasvendelin 2 ปีที่แล้ว

    A bonus question: is the author/presenter left-handed or right handed? Many thanks for a stellar example on how to make a TH-cam video!

  • @MrDemianTV
    @MrDemianTV 7 ปีที่แล้ว

    They say you can grab a person's attention in the first 15 seconds of the video. You nailed it.

  • @spiffmonkey1
    @spiffmonkey1 7 ปีที่แล้ว +1

    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.

  • @Bdjdiwhbkdk
    @Bdjdiwhbkdk 8 ปีที่แล้ว +5

    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-gabbard
      @jackson-gabbard  8 ปีที่แล้ว +16

      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.

    • @revantnayar3408
      @revantnayar3408 7 ปีที่แล้ว

      Jee B to

  • @TheJohn6866
    @TheJohn6866 8 ปีที่แล้ว +3

    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.

  • @Ubemochiya
    @Ubemochiya 4 ปีที่แล้ว +1

    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!

    • @ApurvJaiz
      @ApurvJaiz 4 ปีที่แล้ว

      I guess it would be a lot easier to just flip the video while editing.

  • @ViniciusRodriguesFilenga
    @ViniciusRodriguesFilenga 9 หลายเดือนก่อน

    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.

  • @ranzort
    @ranzort 5 ปีที่แล้ว

    All your vids are so good I have learned to tolerate bad BGM

  • @vinknut
    @vinknut 4 ปีที่แล้ว

    At 6:06 there's a mistake. The largest rectangle isn't 3, it's 4.

  • @sureshchaudhari4465
    @sureshchaudhari4465 9 หลายเดือนก่อน

    Jason Stathum from action hero to Software engineering he learned everything huge respect :P

  • @Shaddymaze
    @Shaddymaze 5 ปีที่แล้ว +2

    High quality all around. Well done, sir! You just earned yourself a sub.

  • @TheJayRap
    @TheJayRap 7 ปีที่แล้ว

    wow this guy is so smart at cursing

  • @g00dvibes47
    @g00dvibes47 7 ปีที่แล้ว

    "...getting a little bit bored with the polite, PC...."
    subscribed.

  • @MrNargleflex
    @MrNargleflex 8 ปีที่แล้ว +3

    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
      @DarcMagikian 2 ปีที่แล้ว

      Is this not also O(n^2)? since there's a while loop inside a for loop?

  • @thequantartist
    @thequantartist 4 ปีที่แล้ว

    Just discovered, this channel. Simply love it!

  • @jacksainthill8974
    @jacksainthill8974 8 ปีที่แล้ว +1

    +Jackson Gabbard
    4:56 You seem to me to be ignoring a size 2x2=4 rectangle at this point.

    • @Nemtrac5
      @Nemtrac5 8 ปีที่แล้ว

      A square is always rectangle, a rectangle is not always a square. Semantics beyond that.

    • @jacksainthill8974
      @jacksainthill8974 8 ปีที่แล้ว

      Nemtrac5
      Am I presumed not to have known that?

    • @whywouldigivemyrealname5162
      @whywouldigivemyrealname5162 8 ปีที่แล้ว

      You literally point out the part at which he goes into the explanation of the 2x2...

    • @Nemtrac5
      @Nemtrac5 8 ปีที่แล้ว +1

      Jack Sainthill there was another guy saying it was a square not rectangle but they deleted their comment.

    • @jacksainthill8974
      @jacksainthill8974 8 ปีที่แล้ว +2

      Nemtrac5
      What a little coward!
      Cheers, you're right, I remember that now.

  • @pradeepravi7591
    @pradeepravi7591 8 ปีที่แล้ว +10

    Dude ..thank you so much... I completed this problem ... :-p
    < Your Largest Rectangle submission got 50.00 points. >

  • @kevincui1631
    @kevincui1631 5 ปีที่แล้ว

    you don't need the weird sound effect. It messes things up

  • @bokonon88
    @bokonon88 8 ปีที่แล้ว +1

    after processing index 3, how is the 1x(4-1) rectangle of height 1 starting at position 1 ignored?

  • @kristymayo494
    @kristymayo494 7 ปีที่แล้ว

    I'm super jealous of your markers. I need blood markers in my life.

  • @tintiniitk
    @tintiniitk 3 ปีที่แล้ว

    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?

  • @jsocial25
    @jsocial25 8 ปีที่แล้ว +91

    Good algo but poor explanation

  • @sajanchoudhary108
    @sajanchoudhary108 5 ปีที่แล้ว

    Finally, someone has succeeded in explaining this question.

  • @crankyinmv
    @crankyinmv 3 ปีที่แล้ว

    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.

  • @StockDC2
    @StockDC2 8 ปีที่แล้ว +2

    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!

  • @sinefinehabitarevolo
    @sinefinehabitarevolo 5 ปีที่แล้ว

    Your step by step explanation is confusing. You explained that at i=2, we dont remove from the position stack because the square actually started at i=1 where height=3 was. But in your code, you are actually popping it out and pushing it back in.

  • @arunraj2527
    @arunraj2527 5 ปีที่แล้ว

    Presentation + effort + explanation = +1 subscriber

  • @reyou7
    @reyou7 5 ปีที่แล้ว

    That's how I do interviews, walk in the room and say "hey, what's up motherfuckers?"

  • @knp281192
    @knp281192 8 ปีที่แล้ว +3

    1) I think you are missing to mention the time & space complexity. Is this the efficient solution ? Kind of like build towards the efficient one, from brute force.
    2) Naming the position stack as starting position stack would have saved me some confusion :P

  • @delmarfenn7068
    @delmarfenn7068 7 ปีที่แล้ว

    Would the largest rectangle be in the empty space and not the "stacks"?

  • @samuellee2131
    @samuellee2131 8 ปีที่แล้ว +16

    Is he like writing backwards

  • @ciphertester1147
    @ciphertester1147 6 ปีที่แล้ว

    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

  • @zhaotianxiong
    @zhaotianxiong 4 ปีที่แล้ว

    You didn't explain why when 3 was poped, you kept its index, but when 2 is poped, you pop the index. The presentation is good but you missed the crucial part of this problem which was when to pop the index stack.

  • @satang500
    @satang500 4 ปีที่แล้ว

    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] ?

  • @ON-ne1rd
    @ON-ne1rd 5 ปีที่แล้ว

    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?

  • @TheMrmartin21
    @TheMrmartin21 7 ปีที่แล้ว

    2×2 is not a rectangle, its a square assuming that the length between each height is the same. so if the 2×2 happened to be saved as the largest, it would be the wrong answer. there would need to be a code somewhere that ignores the 2×2 because the length and width are the same.

    • @ChandanYadav-tw5ms
      @ChandanYadav-tw5ms 7 ปีที่แล้ว

      All squares are rectangles!

    • @TheMrmartin21
      @TheMrmartin21 7 ปีที่แล้ว

      Chandan Yadav disappointingly, you are right. 1 more common sense rule for a rectangle would eliminate this phenomenon. That rule being:
      "That parallel sides must be equal,but not equal to the adjacent parallels side."
      I call this new definition a "rectale". That way a square can never be a rectangle again.😂

    • @ChandanYadav-tw5ms
      @ChandanYadav-tw5ms 7 ปีที่แล้ว

      1. It isn't a common sense rule.
      2. Then, a square isn't a "rectale", but a square is 'Always' a rectangle! :P

    • @TheMrmartin21
      @TheMrmartin21 7 ปีที่แล้ว

      Yeah, I meant that under the Rectale rule. A square isn't a Rectale but a square is a rectangle. But hopefully we would never use rectangle again.
      I guess we should stick with rectangle since we don't have the social or political power to indoctrinate the country into accepting and practicing the "Rectale" shape/rule.😂
      If I had 20 seconds to stop a nuclear launch from destroying the world and I told my assistant "hurry, bring me the rectangle key".
      He could by definition bring me the square key when I needed the other. All of Human advancement could be destroyed over a weird rule that doesn't fully separate these 2 shapes.
      life is funny😂

    • @ChandanYadav-tw5ms
      @ChandanYadav-tw5ms 7 ปีที่แล้ว

      Yeah. But you are not a world saving Terminator hero who doesn't know maths. You are a programmer who should know that when you are asked for a rectangle, you must include squares too. If you still insist on saving the world in your movie using the rectangle key, make sure that it is directed by Nolan so that he can take care of the technical things accurately and have the option between rectangle and circle and not rectangle and square! :P
      It is not a weird rule that separates these shapes. It's just how these are defined. A square is a rectangle, a rectangle is a polygon, a circle is an ellipse... A programmer should know that.

  • @KanagaveluSugumar
    @KanagaveluSugumar 4 ปีที่แล้ว

    Initially i confused that video is not synched with audio and got stuck! But overall it is good effort.

  • @lesterdale7276
    @lesterdale7276 7 ปีที่แล้ว

    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
      @MichielvanderBlonk 2 ปีที่แล้ว

      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.

  • @takanashiouken
    @takanashiouken 4 ปีที่แล้ว

    Is it only me? No matter how many time I read this still don’t get how does tempH*(pos-tempPos) get the area?

  • @dawgalexify
    @dawgalexify 7 ปีที่แล้ว

    Can't we just add a 0 at the end of the histogram array? So we would have a bar of height 0, but that last step where you have to take into consideration the 0 - 1 stacks, you would get 0 so less than 1, you pop 1 and the new area becomes 1*(5-0) = 5(according to the formula)? Just asking, I am not that good when it comes to algorithms.

  • @SephirothITM
    @SephirothITM 7 ปีที่แล้ว

    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.

  • @brifog69
    @brifog69 7 ปีที่แล้ว

    How the fuck did he write those words at the start in reverse so well?

  • @TimZaman
    @TimZaman 8 ปีที่แล้ว

    Very cool problem. Sadly, the implementation of the problem's solution is a bit too large for an interview question.

  • @marionwelton5050
    @marionwelton5050 7 ปีที่แล้ว

    Here’s another approach (literally: bottom up rather than left to right). In pseudo code.
    DEFINE FUNCTION maxSize(INT start, INT stop) RETURNS INT
    LOCAL INT i
    IF start

    • @marionwelton5050
      @marionwelton5050 7 ปีที่แล้ว

      Oops. IF start>stop RETURN 0. Sorry.

  • @4sky
    @4sky 4 ปีที่แล้ว

    I think this is a good algo. But a hard interview question because I think the probability of coming up with this O(n) solution in the middle of an interview having never seen this problem is low.

  • @HardCapGamingOfficial
    @HardCapGamingOfficial 7 ปีที่แล้ว +4

    I laughed so hard when he named the function popThatShit xD

  • @reludragan
    @reludragan 8 ปีที่แล้ว

    I think hStack.push(h); pStack.push(tempPos); should happen only if popThatShit() was called, not necessarily if hStack.length === 0.

  • @Milkyboy92
    @Milkyboy92 8 ปีที่แล้ว +2

    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?

    • @DiogoNeves
      @DiogoNeves 8 ปีที่แล้ว +1

      That's interesting! I'd guess explicitly popping is more... explicit and clear. Can't wait for more opinions/logic on this :)

  • @JFETBJT
    @JFETBJT 8 ปีที่แล้ว

    In the first example (8:16) you are computing size as 1*(5-0), where 5 is out of range of histogram positions. In your implementation pos is always < hist.length. So my question is how would you obtain maxSize == 5, for the first example of histogram [1,3,2,1,2]?

    • @jackson-gabbard
      @jackson-gabbard  8 ปีที่แล้ว +1

      So, this algorithm has two loops. One loop, which I think is the one you've pointed out, only goes from 0 to 4 for this input. And you're right, that loop wouldn't pick up the 1x5 rectangle. Luckily, there's also a second loop. During this loop the position is actually 5, because the final incrementation has happened and pos is now equal to the length of the histogram array (that is, it's 5). So, in this second loop, you're actually using the full width of the histogram in the subtraction part of the formula.

  • @keepallprivate7616
    @keepallprivate7616 8 ปีที่แล้ว

    I wonder if it will going to be really a rectangle at the end of the day.. a square maybe?

  • @subham-raj
    @subham-raj 4 ปีที่แล้ว +3

    *We can do this with only single stack too*

  • @tagadvance
    @tagadvance 8 ปีที่แล้ว

    What might this algorithm be used for? What value is there in knowing the area and position of the largest rectangle?

    • @JacksonGabbard
      @JacksonGabbard 8 ปีที่แล้ว +1

      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.

  • @bennettbmadavana7176
    @bennettbmadavana7176 ปีที่แล้ว

    Thank you so much
    was stuck on this problem for days, finally clicked ✨

  • @AndrewReisdorph
    @AndrewReisdorph 8 ปีที่แล้ว +24

    Now that's a lot of shit popping

  • @sufiyangani6815
    @sufiyangani6815 8 ปีที่แล้ว +1

    when you reached 2 at position 2 you poped 3(as it was bigger than 2)but then you pushed 2 to form a rect of 2*2.
    BUT when you reached 1 at position 3 you poped 2(as it was bigger than 1)but then you didn't pushed 1 to form rect of 1*3??
    please explain..

    • @ghostyzx
      @ghostyzx 8 ปีที่แล้ว

      The algorithm does exactly that if you follow it or run it, it pushes 1*3 when reaching position 3. He probably missed it when doing the explainations...

    • @sufiyangani6815
      @sufiyangani6815 8 ปีที่แล้ว

      Alexandru Coman thanks

  • @kunalsinghgusain2070
    @kunalsinghgusain2070 7 ปีที่แล้ว

    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?".

  • @ruffert100
    @ruffert100 8 ปีที่แล้ว +3

    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?

    • @skripnikalexander
      @skripnikalexander 8 ปีที่แล้ว

      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

    • @ruffert100
      @ruffert100 8 ปีที่แล้ว

      Need to think about that. Thanks :)

    • @itizir
      @itizir 8 ปีที่แล้ว

      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)...

  • @sushrut24
    @sushrut24 4 ปีที่แล้ว

    Is he writing backwards on the glass?

  • @albertoesquivias6073
    @albertoesquivias6073 8 ปีที่แล้ว

    just found your channel, its awesome! keep being yourself and hopefully you upload more soon. thanks!

  • @mrknight411
    @mrknight411 7 ปีที่แล้ว

    I'm naming the pop method popThatShit(), the next time I'm asked to create a dumb Stack class during an interview.

  • @michaelcoppinger786
    @michaelcoppinger786 8 ปีที่แล้ว +4

    Really great vid! Like how you keep the problems interesting and offer entertaining and clear explanations. Enjoy your work a lot :)

  • @souparnomajumder
    @souparnomajumder 2 ปีที่แล้ว

    are you fluently writing form right to left with the characters mirrored !

  • @JackBauerDev
    @JackBauerDev 8 ปีที่แล้ว

    What is the complexity for this algo? This can be done in O(n) if you drop the stacks and only use a few variables using intelligent linear drag.

    • @someone6949
      @someone6949 8 ปีที่แล้ว +1

      This algorithm is clearly O(n). You can only ever add something to the stack once and pop it off once. Stack operations are O(1), so linear on size of input histogram.

  • @randomshotz13
    @randomshotz13 8 ปีที่แล้ว

    I'd be very interested in seeing a solution with non uniform class widths I imagine a similar approach but where the total width passed through would be stored rather than the starting location. If given the question from the video in an interview. Would the interviewer prefer I simplify the problem and assume unity or that I handled for other cases?

  • @sarscov9854
    @sarscov9854 3 ปีที่แล้ว

    I was going to comment that you should use let instead of var, but then I realized this was made in 2016.

  • @israelmcculley2927
    @israelmcculley2927 3 ปีที่แล้ว

    If you use a Tuple you can just use 1 stack.

  • @reapertheunique
    @reapertheunique 8 ปีที่แล้ว +8

    This is a coding interview example? Holy shit! you would have to solve this while some dudes are watching your every move?

    • @Oreoboy101
      @Oreoboy101 8 ปีที่แล้ว +5

      I had this in an interview today. FML. I bombed it.

  • @gokukakarot6323
    @gokukakarot6323 4 ปีที่แล้ว

    Fuuuuuucccckkkk, this is mindblowing explanation. Please make more videos like this. Also normally I watch videos at 1.5x this is the first video I watched at 0.75x

  • @TomusMedia
    @TomusMedia 8 ปีที่แล้ว

    I don't understand this, how do you write so good backwards?

  • @techdnb1
    @techdnb1 8 ปีที่แล้ว +1

    I like the explanations a lot, some ideas:
    - I watched a lot of Khan Academy videos, the style is similar but you don't see the person in the background, I find that more focused on the problem / less distracting.
    - I could use pauses at critical parts where I have to realize something. The pace is quite high overall for me to follow everything.

  • @aditya070791
    @aditya070791 6 ปีที่แล้ว

    Loved the video ! Infinitely more interesting than other ones out there.

  • @ayoaloko1453
    @ayoaloko1453 8 ปีที่แล้ว +10

    do you write backwards on the board

    • @crazybird1649
      @crazybird1649 8 ปีที่แล้ว +10

      oh dear god.. =) No he flips the video in post to make it correct for the camera.

    • @jackson-gabbard
      @jackson-gabbard  8 ปีที่แล้ว +50

      Mattias Stahre, that's not what I heard. I heard he actually turns the camera around backwards.

    • @xthebumpx
      @xthebumpx 8 ปีที่แล้ว

      It's easier when you're lefthanded like he is in the video.

  • @programminginterviewprep1808
    @programminginterviewprep1808 7 ปีที่แล้ว

    I am wondering how did you take this video? It looks very interesting!

  • @EvanKozliner
    @EvanKozliner 4 ปีที่แล้ว

    This question is wild. Awesome explanation :)

  • @justingivens217
    @justingivens217 8 ปีที่แล้ว +1

    Awesome explanation of problem and solution! Keep them coming!!

  • @sharinganuser1539
    @sharinganuser1539 4 ปีที่แล้ว

    for a minute i forgot i'm studying....so many signature lines...even batman cried....i don't know much js...but i continued anyways......

  • @kevinxin1545
    @kevinxin1545 8 ปีที่แล้ว +4

    Wait What?!?! How could you write backwards like that?????

    • @myaccount99000
      @myaccount99000 8 ปีที่แล้ว +1

      Xingzhe Xin He's actually right handed :P

    • @kevinxin1545
      @kevinxin1545 8 ปีที่แล้ว

      how is the person opposite while the words he write not?

    • @myaccount99000
      @myaccount99000 8 ปีที่แล้ว +6

      Xingzhe Xin lol because if he's facing the camera from the other side of the glass while writing with his right hand.... then the text would appear backwards. So he then flips the video (making it appear as though he's left handed) and then the text is in the correct direction again.

    • @HardCapGamingOfficial
      @HardCapGamingOfficial 7 ปีที่แล้ว

      Also, note that the logo on his t-shirt is on the wrong side :P

  • @tienanh2007
    @tienanh2007 8 ปีที่แล้ว

    How does the letters just slide off like that ?

  • @NeetCode
    @NeetCode 4 ปีที่แล้ว +1

    I can't link it, but I've made a video for this problem that is MUCH MORE intuitive and might be helpful for some people. =D​

  • @thedrumify
    @thedrumify 7 ปีที่แล้ว

    I don't know JavaScript, but isn't there an error in the while condition?

  • @MaxHeckelIsMe
    @MaxHeckelIsMe 8 ปีที่แล้ว +2

    Great video, going to binge watch the rest now.

  • @soumya5200
    @soumya5200 7 ปีที่แล้ว

    How did you create a video that makes you look like you are writing on glass?