Minimum Number of Arrows to Burst Balloons - Leetcode 452 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link:leetcode.com/problems/minimum...
0:00 - Read the problem
0:14 - Drawing Explanation
8:46 - Coding Explanation
leetcode 452
#neetcode #leetcode #python

[@1vader]

Notice that you are never using prev[0]. You don't actually need to merge intervals, it's enough to just keep track of the earliest ending point. That's the latest point where the arrow can be shot to pop the balloons so far and at that point, all the other overlapping balloons are also popped and therefore become completely irrelevant.

[@yang5843]

A good follow-up question to intervals from yesterday's

[@DeathSugar]

i've made a mess yesterday compared to today's

[@sanchitbajaj02]

When I read this problem, it goes over my head but after a few minutes of explanation, I thought it was almost the same as yesterday

[@DebopriyoBasu]

Not sure about balloons, but my head did burst. This is an excellent explanation!

[@elizabeth00653]

Love your clear engaging solutions

[@dineshkumarkb1372]

Wow. Initialising the arrow count to n and decrementing was clever. I've always tripped myself up initialising result to 0 or 1. But yeah, like you said, having the result set to 1 is more intuitive as we already have a balloon in our prev variable. Ofcourse it goes without saying, Great work as always :)

[@MP-ny3ep]

Great explanation as always. Thank you

[@SC2Edu]

Super clear as usual, thanks

[@pastori2672]

what if they miss

[@kanishkkala16]

my intuition was also to decrement from n

[@sauravsingh4497]

For once when I read the title I thought the problem was the crackhead problem "burst balloons"

[@LlamaBG]

awesome

[@eleven-2806]

can someone tell me why this cant be solved by merge intervals and returning size?

[@mahesh_bvn]

Hey, can you solve leetcode 790(Domino and Tromino Tiling). Seems baffling

[@sidhartheleswarapu]

We can just track the end of the previous interval in a variable prevEnd. No need to care about the starting value of the previous interval.

[@pastori2672]

btw why is the time complexity nlong instead of n ** 2 because apparently min() takes linear time and its nested within a loop

[@1vader]

min() takes linear time over the number of elements it has to select the minimum from, which in this case is always 2, a constant. You have to be very careful with general statements like "f takes linear amount of time" without considering its inputs in relation to the input of the actual problem.

[@pastori2672]

@@1vader oh right you're right

[@yang5843]

Java Solution class Solution { public int findMinArrowShots(int[][] points) { Arrays.sort(points,(a,b)->a[0]==b[0]?Integer.compare(a[1],b[1]):Integer.compare(a[0],b[0])); int rc = points.length; int[] prev = points[0]; for (int i=1;i

[@ObaidKnight]

Neet I'm losing motivation, I need some encouragement

[@luciferdesuza1541]

Ask your hand for it😂

[@joshk9571]

enjoy being broke. someone has to flip the burgers for me

[@yang5843]

My approach was to use greedy, have a left and right bound for the first balloon, if the next balloon fits inside the bound, then don't do anything, and reduce the left and right bounds to be the min/max of the two balloons, otherwise increase the return value and set the left and right bound to be the new balloon. class Solution { public int findMinArrowShots(int[][] points) { int rc = 0; Arrays.sort(points,(a,b)->a[0]==b[0]?a[1]-b[1]:a[0]-b[0]); int i = 0; long minL = Long.MIN_VALUE; long minR = Long.MIN_VALUE; while ( i < points.length ) { int l = points[i][0]; int r = points[i][1]; // System.out.println(l+" "+r); if ( minL