Sorting as a pattern

Many problems that look like they need comparing all pairs become a single pass once the data is sorted. The sort costs O(n log n) and the scan O(n), which is usually acceptable, and it uses no extra hash structures.

Examples: find any duplicate (compare neighbours), the minimum difference between two elements (it is between neighbours), and 3Sum (sort, then two pointers for each first element).

1static int minimumDifference(int[] arr) {
2    int[] a = arr.clone();
3    Arrays.sort(a);
4    int best = Integer.MAX_VALUE;
5    for (int i = 1; i < a.length; i++) {
6        best = Math.min(best, a[i] - a[i - 1]);   // the closest pair is always adjacent after sorting
7    }
8    return best;
9}

To group items that are “the same” under some definition, sort them by a key that captures that definition, or map each item to a canonical key. Anagrams share the same sorted letters, so the sorted string is a natural key.

Sorting the whole list groups equal keys together (O(n log n)); a HashMap<key, List> groups them without sorting the list (expected O(n), plus the cost of computing each key).

1static Collection<List<String>> groupAnagrams(String[] words) {
2    Map<String, List<String>> groups = new HashMap<>();
3    for (String w : words) {
4        char[] key = w.toCharArray();
5        Arrays.sort(key);                                     // canonical form: letters in order
6        groups.computeIfAbsent(new String(key), k -> new ArrayList<>()).add(w);
7    }
8    return groups.values();
9}

Sort intervals by start. Then two intervals overlap only if one starts before the previous one ends, so a single scan can merge them: extend the last merged interval or start a new one.

Enter your own start, end pairs in the animation. The top lane shows the intervals in sorted order; the bottom lane shows the merged result growing.

1public static List<int[]> merge(int[][] intervals) {
2    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));   // sort by start
3    List<int[]> merged = new ArrayList<>();
4    for (int[] cur : intervals) {
5        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
6        if (last != null && cur[0] <= last[1]) {
7            last[1] = Math.max(last[1], cur[1]);     // overlap: extend
8        } else {
9            merged.add(cur);                         // gap: start a new interval
10        }
11    }
12    return merged;
13}

A sweep line moves through time and processes events in sorted order: each start adds one to a running count, each end subtracts one. The maximum running count is the maximum number of simultaneous events, which is the number of meeting rooms needed.

Sorting starts and ends separately and walking them with two pointers avoids building event objects. With half-open intervals [start, end), an end at time t frees its room before a start at the same t takes one, which is why the loop uses <=.

1public static int minRooms(int[][] meetings) {     // [start, end), end is exclusive
2    int n = meetings.length;
3    int[] starts = new int[n], ends = new int[n];
4    for (int i = 0; i < n; i++) { starts[i] = meetings[i][0]; ends[i] = meetings[i][1]; }
5    Arrays.sort(starts);
6    Arrays.sort(ends);
7    int rooms = 0, best = 0, e = 0;
8    for (int s = 0; s < n; s++) {
9        while (ends[e] <= starts[s]) { e++; rooms--; }   // meetings that ended free a room
10        rooms++;
11        best = Math.max(best, rooms);
12    }
13    return best;
14}

Real problems sort by derived keys: by end time for interval scheduling, by frequency then value, by distance from a point. Build the comparator from Comparator.comparing and chain tie-breakers with thenComparing.

Sorting by end time is the key step in the greedy “maximum non-overlapping intervals” algorithm: always keep the interval that finishes first. Sorting by start time would be wrong for that problem.

1// most frequent first, ties broken by smaller value
2Integer[] boxed = Arrays.stream(nums).boxed().toArray(Integer[]::new);
3Map<Integer, Long> freq = Arrays.stream(nums).boxed()
4    .collect(Collectors.groupingBy(x -> x, Collectors.counting()));
5Arrays.sort(boxed, Comparator.<Integer, Long>comparing(freq::get).reversed()
6                             .thenComparing(Comparator.naturalOrder()));
7
8// interval scheduling: sort by end time
9Arrays.sort(intervals, Comparator.comparingInt(iv -> iv[1]));