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.
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 :)
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];
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.
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
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.
Not sure about balloons, but my head did burst. This is an excellent explanation!
A good follow-up question to intervals from yesterday's
i've made a mess yesterday compared to today's
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
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 :)
could not burst ballons with minimum arrows, but bursted my head with just this one question!
Love your clear engaging solutions
my intuition was also to decrement from n
what if they miss
For once when I read the title I thought the problem was the crackhead problem "burst balloons"
Super clear as usual, thanks
Great explanation as always. Thank you
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.
Hey, can you solve leetcode 790(Domino and Tromino Tiling). Seems baffling
can someone tell me why this cant be solved by merge intervals and returning size?
awesome
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
btw why is the time complexity nlong instead of n ** 2 because apparently min() takes linear time and its nested within a loop
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.
@@1vader oh right you're right
I get the intution. Fail to proove that this approach will give the minimum. And no one discuss this too ? Am i overthinking ??
Neet I'm losing motivation, I need some encouragement
Ask your hand for it😂
enjoy being broke. someone has to flip the burgers for me
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