Advanced Sorting Applications (Intervals, Custom Comparators)

Interval Problems: Sorting as the Prerequisite

For almost all interval-based challenges, the first step is sorting by the start point. Occasionally, sorting by the end point is required for specific greedy optimizations.

Merge Intervals (LeetCode 56)

int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort by start point ascending
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> result = new ArrayList<>();
    int[] currentInterval = intervals[0];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] <= currentInterval[1]) {
            // Overlap detected: expand the current interval's end if necessary
            currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
        } else {
            // No overlap: finalize current and move to the next
            result.add(currentInterval);
            currentInterval = intervals[i];
        }
    }
    result.add(currentInterval);
    return result.toArray(new int[0][]);
}

Key Rule: Two intervals overlap if nextStart <= currentEnd.

Non-overlapping Intervals (LeetCode 435) — Sort by End Point

To minimize removals, we want to maximize the number of preserved intervals. This is a classic greedy problem: always pick the interval that finishes earliest to leave the most space for others.

int eraseOverlapIntervals(int[][] intervals) {
    // Greedy strategy: Sort by finish time (end point)
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
    
    int count = 1; // Number of non-overlapping intervals kept
    int end = intervals[0][1];
    
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            // Found another non-overlapping interval
            count++;
            end = intervals[i][1];
        }
    }
    return intervals.length - count;
}

Why sort by end point? Choosing the earliest-ending interval minimizes restrictions on all future choices.

Minimum Number of Arrows to Burst Balloons (LeetCode 452)

Identical logic to the previous problem, but count the arrows (the "ends") needed to pierce all ranges.

int findMinArrowShots(int[][] points) {
    // Use Integer.compare to avoid subtraction overflow
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    
    int arrows = 1;
    int end = points[0][1];
    
    for (int i = 1; i < points.length; i++) {
        // If the next balloon starts AFTER the current arrow limit, we need a new arrow
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}

The Custom Comparator Trap

Largest Number (LeetCode 179)

Concatenate numbers to form the largest possible total value. The sorting rule: compare sequence AB with BA.

String largestNumber(int[] nums) {
    String[] strs = Arrays.stream(nums)
            .mapToObj(String::valueOf)
            .toArray(String[]::new);
            
    // Custom sort: if (b+a) > (a+b), b should come before a
    Arrays.sort(strs, (a, b) -> (b + a).compareTo(a + b));
    
    if (strs[0].equals("0")) return "0"; // Edge case: all zeros [0, 0]
    return String.join("", strs);
}

⚠️ Avoid Arithmetic Overflows in Comparators

// DANGEROUS: If a is huge positive and b is huge negative, (a - b) will overflow
Arrays.sort(arr, (a, b) -> a - b);

// SAFE: Use the built-in compare method
Arrays.sort(arr, (a, b) -> Integer.compare(a, b));

Bucket Sort Strategies

Top K Frequent Elements (LeetCode 347)

Frequencies are naturally bounded by $N$. We can create $N+1$ buckets where the index is the frequency.

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freqMap = new HashMap<>();
    for (int n : nums) freqMap.merge(n, 1, Integer::sum);
    
    // Buckets: index = frequency, value = list of numbers with that frequency
    List<Integer>[] buckets = new List[nums.length + 1];
    for (var entry : freqMap.entrySet()) {
        int f = entry.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(entry.getKey());
    }
    
    int[] result = new int[k];
    int ptr = 0;
    for (int i = buckets.length - 1; i >= 0 && ptr < k; i--) {
        if (buckets[i] != null) {
            for (int num : buckets[i]) {
                result[ptr++] = num;
                if (ptr == k) break;
            }
        }
    }
    return result;
}

Complexity: $O(N)$, outperforming the standard $O(N \log N)$ sorting approaches.

Recognition Summary