7. Sorting & Utilities

Note

Why this matters for DSA Standard sorting, custom element orderings (e.g., sorting intervals or grid coordinates), and binary search are used in a massive number of search and greedy algorithms. Furthermore, in competitive programming, using standard input parsers can easily result in TLE. A robust understanding of utility libraries and Fast I/O is a necessity.

7.1 Custom Sorting with Comparators & Lambdas

Java provides Arrays.sort() for arrays and Collections.sort() for lists. By default, they sort in ascending order.

1. Reverse Sorting (Descending)

Warning

You cannot sort primitive arrays (like int[]) in descending order directly using built-in comparators. Java comparators only work on objects (reference types). Workaround: Convert to wrapper types (like Integer[]), or sort ascending and reverse manually.

java

import java.util.Arrays;
import java.util.Collections;

Integer[] arr = {3, 1, 4, 1, 5};
Arrays.sort(arr, Collections.reverseOrder()); // [5, 4, 3, 1, 1]

2. Custom Sorting (Lambdas)

For sorting 2D arrays (like intervals) or custom objects, pass a lambda expression:

java

// Example: Sort intervals by start time ascending. If start times match, sort by end time descending.
int[][] intervals = {{1, 3}, {2, 6}, {1, 5}};

Arrays.sort(intervals, (a, b) -> {
    if (a[0] != b[0]) {
        return a[0] - b[0]; // Sort ascending by index 0
    } else {
        return b[1] - a[1]; // Sort descending by index 1
    }
});
// Result: {{1, 5}, {1, 3}, {2, 6}}

7.2 Arrays & Collections Utility classes

java

import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;

// --- Arrays Utilities ---
int[] nums = {10, 20, 30, 40};

// Copying range (useful for splitting arrays)
int[] subArray = Arrays.copyOfRange(nums, 1, 3); // index 1 to 2 -> [20, 30]
int[] fullCopy = Arrays.copyOf(nums, nums.length);

// Comparison
boolean isEqual = Arrays.equals(nums, fullCopy); // true

// --- Collections Utilities (Lists only) ---
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 2));

Collections.reverse(list);       // Reverses list -> [2, 3, 2, 1]
Collections.shuffle(list);       // Randomizes elements
int min = Collections.min(list); // 1
int max = Collections.max(list); // 3
int freq = Collections.frequency(list, 2); // 2 (frequency of '2')

7.3 Binary Search

Binary search runs in $O(\log N)$ time. The collection must be sorted beforehand.

java

import java.util.Arrays;

int[] sortedNums = {10, 20, 30, 40, 50};
int index = Arrays.binarySearch(sortedNums, 30); // returns 2

// If element is not found, it returns a negative value:
// -(insertion_point) - 1
int missingIndex = Arrays.binarySearch(sortedNums, 25); // returns -3 (insertion point is index 2)

Manual Binary Search Skeleton (Iterative)

java

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // Prevents overflow: (low+high)/2
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // Not found
}

7.4 Math & Helper Algorithms

These number theory and math helpers are crucial for many math-heavy DSA topics.

java

// 1. Greatest Common Divisor (GCD / HCF) - Euclid's Algorithm O(log(min(a,b)))
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 2. Least Common Multiple (LCM)
public static int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

// 3. Fast Exponentiation (a^b in O(log b) time) - Binary exponentiation
public static long fastPower(long base, long exp) {
    long res = 1;
    while (exp > 0) {
        if ((exp & 1) == 1) res *= base; // if odd exponent, multiply base
        base *= base;
        exp >>= 1; // divide exponent by 2 (right shift)
    }
    return res;
}

7.5 Fast I/O (Competitive Programming)

Standard Scanner is too slow for large inputs ( $> 10^5$ values). Use this custom FastScanner template, which leverages BufferedReader and StringTokenizer for maximum performance.

java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        FastScanner fs = new FastScanner();
        // Use fs.nextInt() or fs.next() for high-speed input reading
    }
}

Practice Drill

java

// Try implementing these:
// 1. Sort a 2D array of coordinates representing intervals: {start, end} by start time ascending; if start times are equal, sort by end time ascending.
// 2. Write a binary search implementation that finds the index of the first occurrence of a duplicate element in a sorted array (e.g. {1, 2, 2, 2, 3}, target=2 -> returns index 1).
// 3. Write a helper method that computes the GCD of an array of integers.
// 4. Implement a custom comparator that sorts a List of strings in descending order of their lengths.

💡 Click for Solutions

java

import java.util.*;

public class SortingUtilitiesDrill {
    public static void main(String[] args) {
        // 1. Interval sorting
        int[][] intervals = {{1, 4}, {2, 3}, {1, 2}};
        sortIntervals(intervals);
        System.out.println("Sorted intervals: " + Arrays.deepToString(intervals));
        // Expected: [[1, 2], [1, 4], [2, 3]]

        // 2. First occurrence binary search
        int[] nums = {1, 2, 2, 2, 3};
        System.out.println("First occurrence of 2: " + findFirstOccurrence(nums, 2)); // 1

        // 3. GCD of an array
        int[] arr = {12, 18, 24};
        System.out.println("GCD of array: " + findArrayGCD(arr)); // 6

        // 4. Sort strings by length descending
        List<String> words = new ArrayList<>(Arrays.asList("go", "python", "java", "c"));
        words.sort((s1, s2) -> s2.length() - s1.length());
        System.out.println("Strings sorted by length: " + words);
        // Expected: [python, java, go, c]
    }

    // 1. Sort intervals
    public static void sortIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            }
            return a[1] - b[1];
        });
    }

    // 2. Binary search first occurrence
    public static int findFirstOccurrence(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int result = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                result = mid; // record candidate index
                high = mid - 1; // keep searching on the left side
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    // 3. Array GCD
    public static int findArrayGCD(int[] arr) {
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
            if (result == 1) return 1; // Early exit: GCD cannot be smaller than 1
        }
        return result;
    }

    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

← Stack, Queue & Deque | Next → Bit Manipulation & Characters