Simple Java Solution (With Explanation)


  • 0
    Q

    This is my solution:

    First, we sort the 2d Array.
    Then, starting with the first balloon, we calculate the upperbound, and adjust it as we go through the balloon.

    If the lowerbound of the next balloon is smaller than the current upperbound, the existing arrow will hit, so we keeps going.
    Else, (if the lowerbound if the next balloon is larger than current upperbound), then it's out of range and we'd need another arrow.

    public static int findMinArrowShots(int[][] points) {
                    // Sort the array of balloons
    		Arrays.sort(points, new Comparator<int[]>() {
    			public int compare(int[] a, int[] b) {
    				return Integer.compare(a[0], b[0]);
    			}
    		});
    
    		if (points.length == 0) return 0; //check for empty array
    		int upperBound = points[0][1]; //the first upperbound of the first balloon
    		int arrowCount = 1; // the first arrow
    		for (int i = 0; i < points.length - 1; i++) {
    			// See if the next balloon is out of range
    			if (upperBound < points[i + 1][0]) {
    				arrowCount++;
    				upperBound = points[i + 1][1];
    			}
    			else {
                                    //Adjust the upperbound in case the next balloon is smaller than the current one
    				upperBound = Math.min(upperBound, points[i + 1][1]);
    				continue;
    			}
    		}
    		return arrowCount;
    	}
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.