Sorting Applications: H-Index, Wiggle Sort, and Scheduling

H-Index (LeetCode 274)

The H-Index is defined as follows: A scientist has index $H$ if at least $H$ of their $N$ papers have each been cited at least $H$ times.

Approach 1: Enumeration after Sorting ($O(N \log N)$)

public int hIndex(int[] citations) {
    Arrays.sort(citations);
    int n = citations.length;
    // Iterate from largest to smallest number of citations
    for (int i = 0; i < n; i++) {
        int h = n - i; // Number of papers with at least citations[i] citations
        if (citations[i] >= h) return h;
    }
    return 0;
}

Approach 2: Counting Sort ($O(N)$)

Since H cannot exceed the total number of papers $N$, we can use buckets up to size $N$.

public int hIndex(int[] citations) {
    int n = citations.length;
    int[] bucket = new int[n + 1];
    for (int c : citations) {
        bucket[Math.min(c, n)]++; // Any citations beyond n are capped at n
    }
    
    int paperCount = 0;
    for (int h = n; h >= 0; h--) {
        paperCount += bucket[h];
        if (paperCount >= h) return h;
    }
    return 0;
}

Wiggle Sort (LeetCode 280 / 324)

Wiggle Sort I: Adjust in-place ($nums[0] \le nums[1] \ge nums[2] \dots$)

Rule: For an even index $i$, if $nums[i] > nums[i+1]$, swap. For an odd index $i$, if $nums[i] < nums[i+1]$, swap.

public void wiggleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        boolean shouldBeSmaller = (i % 2 == 0);
        if (shouldBeSmaller) {
            if (nums[i] > nums[i+1]) swap(nums, i, i+1);
        } else {
            if (nums[i] < nums[i+1]) swap(nums, i, i+1);
        }
    }
}

Wiggle Sort II: Strict Inequality ($nums[0] < nums[1] > nums[2] \dots$)

Requires more precision. The standard approach is picking the median and interleaving small/large numbers.

public void wiggleSortII(int[] nums) {
    int n = nums.length;
    int[] sorted = nums.clone();
    Arrays.sort(sorted); // Simplified version using O(N log N) sorting
    
    int mid = (n - 1) / 2;
    int right = n - 1;
    
    // Interleave: smaller values on even indices, larger values on odd indices
    for (int i = 0; i < n; i++) {
        nums[i] = (i % 2 == 0) ? sorted[mid--] : sorted[right--];
    }
}

Minimum Time to Repair Cars (LeetCode 2594)

Multiple mechanics with rank $r$ can repair $k$ cars in $r \cdot k^2$ minutes. Find the minimum time to repair all cars.

Strategy: We can binary search the result time $T$. For a given $T$, a mechanic with rank $r$ can repair $\sqrt{T/r}$ cars.

public long repairCars(int[] ranks, int cars) {
    long left = 1, right = (long) ranks[0] * cars * cars;
    while (left < right) {
        long mid = left + (right - left) / 2;
        if (canRepairAll(ranks, cars, mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

private boolean canRepairAll(int[] ranks, int cars, long t) {
    long totalCarsSupported = 0;
    for (int r : ranks) {
        totalCarsSupported += (long) Math.sqrt((double) t / r);
        if (totalCarsSupported >= cars) return true;
    }
    return false;
}

DI String Match (LeetCode 942)

Given a string s, find a permutation that satisfies the increase/decrease patterns.

public int[] diStringMatch(String s) {
    int n = s.length();
    int low = 0, high = n;
    int[] result = new int[n + 1];
    
    for (int i = 0; i < n; i++) {
        // If 'I'ncrease, take the smallest remaining value
        // If 'D'ecrease, take the largest remaining value
        result[i] = (s.charAt(i) == 'I') ? low++ : high--;
    }
    result[n] = low; // Final remaining number
    return result;
}

Summary Selection Table