Advanced Sorting Techniques: K-th Ordinal Statistics and Counting Inversions

Introduction to the Lesson

Welcome to this insightful session, where we aim to master the complexities of the illustrious applications of sorting algorithms . Today's voyage links two problems: "Find the K-th Ordinal Statistic in a List" and "Count the Number of Inversions in a List" . These problems mirror practical scenarios, and the efficient techniques used to solve them present valuable demonstrations of the application of sort algorithms. Solving these two problems, we'll see how Quick Sort and Merge Sort knowledge applies here and helps provide efficient implementations for both questions. Let's dive into these captivating problems!

Problem 1: Find the K-th Ordinal Statistic in a List

Our first problem presents a list of integers and the number k . The challenge is finding the k -th smallest element in that given list. To further elucidate, k starts from 1, so for k = 1, you are seeking to find the smallest element; if k = 2, you're searching for the second smallest element, and so on. By the conclusion of this lesson, you'll be highly skilled at performing this task!

Problem 1: Naive Approaches

O(n^2)

Problem 1: Efficient Approach Explanation

Sorting steps in here to offer an efficient solution! The Quick Sort algorithm, a splendid application of divide and conquer, can solve this problem more efficiently. By selecting the right pivot for partitioning, the input list is divided into two: a left partition, which contains elements less than the pivot, and a right partition, which includes elements greater than the pivot. If the pivot's position after elements repartition is the same as k, we have the k -th smallest element. If k is less than the pivot's position, the task is carried forward on the left partition; otherwise, on the right partition.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Java

Arrays.sort(inputArray);
return inputArray[k - 1];

Java

static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start;

    for(int j = start + 1; j <= end; j++) {
        if(arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i];
    arr[i] = arr[start];
    arr[start] = temp;

    return i;
}

static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start;

    for(int j = start + 1; j <= end; j++) {
        if(arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i];
    arr[i] = arr[start];
    arr[start] = temp;

    return i;
}

Java

import java.util.*;

class Solution {
    public static int findKthSmallest(int[] numbers, int k) {
        if(numbers == null || numbers.length < k)
            return Integer.MIN_VALUE;
        return kthSmallest(numbers, 0, numbers.length - 1, k);
    }

    static int kthSmallest(int[] arr, int start, int end, int k) {
        if (k > 0 && k <= end - start + 1) {
            int pos = partition(arr, start, end);

            if (pos - start == k - 1) {
                return arr[pos];
            }

            if (pos - start > k - 1) {
                return kthSmallest(arr, start, pos - 1, k);
            }

            return kthSmallest(arr, pos + 1, end, k - pos + start - 1);
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 7, 2, 4, 2, 1, 6};
        System.out.println(findKthSmallest(numbers, 5));  // It should print 4
    }
}

import java.util.*;

class Solution {
    public static int findKthSmallest(int[] numbers, int k) {
        if(numbers == null || numbers.length < k)
            return Integer.MIN_VALUE;
        return kthSmallest(numbers, 0, numbers.length - 1, k);
    }

    static int kthSmallest(int[] arr, int start, int end, int k) {
        if (k > 0 && k <= end - start + 1) {
            int pos = partition(arr, start, end);

            if (pos - start == k - 1) {
                return arr[pos];
            }

            if (pos - start > k - 1) {
                return kthSmallest(arr, start, pos - 1, k);
            }

            return kthSmallest(arr, pos + 1, end, k - pos + start - 1);
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 7, 2, 4, 2, 1, 6};
        System.out.println(findKthSmallest(numbers, 5));  // It should print 4
    }
}

Java

public class Result {
    public int[] sorted;
    public long inversions;

    public Result(int[] sorted, long inversions) {
        this.sorted = sorted;
        this.inversions = inversions;
    }
}

public class Result {
    public int[] sorted;
    public long inversions;

    public Result(int[] sorted, long inversions) {
        this.sorted = sorted;
        this.inversions = inversions;
    }
}

Java

public Result countInversions(int[] arr) {
    if (arr.length <= 1) {
        return new Result(arr, 0);
    }
    int middle = arr.length / 2;
    Result left = countInversions(Arrays.copyOfRange(arr, 0, middle));
    Result right = countInversions(Arrays.copyOfRange(arr, middle, arr.length));
    Result result = mergeAndCountInversions(left.sorted, right.sorted);
    return new Result(result.sorted, left.inversions + right.inversions + result.inversions);
}

private Result mergeAndCountInversions(int[] left, int[] right) {
    int[] merged = new int[left.length + right.length];
    int i = 0, j = 0;
    long inversions = 0;
    for(int k = 0; k < merged.length; k++) {
        if (i < left.length && (j >= right.length || left[i] <= right[j])) {
            merged[k] = left[i++];
        } else {
            merged[k] = right[j++];
            inversions += left.length - i;
        }
    }
    return new Result(merged, inversions);
}

public Result countInversions(int[] arr) {
    if (arr.length <= 1) {
        return new Result(arr, 0);
    }
    int middle = arr.length / 2;
    Result left = countInversions(Arrays.copyOfRange(arr, 0, middle));
    Result right = countInversions(Arrays.copyOfRange(arr, middle, arr.length));
    Result result = mergeAndCountInversions(left.sorted, right.sorted);
    return new Result(result.sorted, left.inversions + right.inversions + result.inversions);
}

private Result mergeAndCountInversions(int[] left, int[] right) {
    int[] merged = new int[left.length + right.length];
    int i = 0, j = 0;
    long inversions = 0;
    for(int k = 0; k < merged.length; k++) {
        if (i < left.length && (j >= right.length || left[i] <= right[j])) {
            merged[k] = left[i++];
        } else {
            merged[k] = right[j++];
            inversions += left.length - i;
        }
    }
    return new Result(merged, inversions);
}

Java

static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int i = start;

    for(int j = start + 1; j <= end; j++) {
        if(arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i];
    arr[i] = arr[start];
    arr[start] = temp;

    return i;
}

Java

import java.util.*;

class Solution {
    public static int findKthSmallest(int[] numbers, int k) {
        if(numbers == null || numbers.length < k)
            return Integer.MIN_VALUE;
        return kthSmallest(numbers, 0, numbers.length - 1, k);
    }

    static int kthSmallest(int[] arr, int start, int end, int k) {
        if (k > 0 && k <= end - start + 1) {
            int pos = partition(arr, start, end);

            if (pos - start == k - 1) {
                return arr[pos];
            }

            if (pos - start > k - 1) {
                return kthSmallest(arr, start, pos - 1, k);
            }

            return kthSmallest(arr, pos + 1, end, k - pos + start - 1);
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args) {
        int[] numbers = {1, 7, 2, 4, 2, 1, 6};
        System.out.println(findKthSmallest(numbers, 5));  // It should print 4
    }
}

Java

public class Result {
    public int[] sorted;
    public long inversions;

    public Result(int[] sorted, long inversions) {
        this.sorted = sorted;
        this.inversions = inversions;
    }
}

Java

public Result countInversions(int[] arr) {
    if (arr.length <= 1) {
        return new Result(arr, 0);
    }
    int middle = arr.length / 2;
    Result left = countInversions(Arrays.copyOfRange(arr, 0, middle));
    Result right = countInversions(Arrays.copyOfRange(arr, middle, arr.length));
    Result result = mergeAndCountInversions(left.sorted, right.sorted);
    return new Result(result.sorted, left.inversions + right.inversions + result.inversions);
}

private Result mergeAndCountInversions(int[] left, int[] right) {
    int[] merged = new int[left.length + right.length];
    int i = 0, j = 0;
    long inversions = 0;
    for(int k = 0; k < merged.length; k++) {
        if (i < left.length && (j >= right.length || left[i] <= right[j])) {
            merged[k] = left[i++];
        } else {
            merged[k] = right[j++];
            inversions += left.length - i;
        }
    }
    return new Result(merged, inversions);
}

Introduction to the Lesson

Problem 1: Find the K-th Ordinal Statistic in a List

Problem 1: Naive Approaches

Problem 1: Efficient Approach Explanation

Join the 1M+ learners on CodeSignal

Problem 1: Solution Building – Partition

Problem 1: Solution Building – Main Logic

Problem 2: Count the Number of Inversions in a List

Problem 2: Efficient Approach Explanation

Problem 2: Solution Building – Supporting Class

Lesson Summary

Practice Exercises