Count Smaller elements

JavaView on GFG

Problem Overview

For each element, count how many elements to its right are smaller.

Intuition

For each element, count how many elements to its right are smaller. Merge sort or BIT.

Algorithm

1BIT/Fenwick tree: process right to left. For each element: query(val-1) gives count of smaller elements seen so far. Update BIT.

Common Pitfalls

• Same as LC 315. Coordinate compress if values are large. Merge sort approach also O(n log n).

Count Smaller elements.java

Java

// Approach: Merge sort or BIT/Fenwick tree. For each element, count elements to its right that are smaller.
// Time: O(n log n) Space: O(n)
class Solution {
    int[] constructLowerArray(int[] arr) {
        // code here
        int n = arr.length;

        int[] result = new int[n];
        int[] indexes = new int[n];
        for (int i = 0; i < n; i++) {
            indexes[i] = i;
        }
        mergeSort(arr, indexes, result, 0, n - 1);
        return result;
        // code here
    }

    private void mergeSort(int[] arr, int[] indexes, int[] result, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(arr, indexes, result, start, mid);
        mergeSort(arr, indexes, result, mid + 1, end);
        merge(arr, indexes, result, start, mid, end);
    }

    private void merge(int[] arr, int[] indexes, int[] result, int start, int mid, int end) {
        int[] tempIndexes = new int[end - start + 1];
        int left = start;
        int right = mid + 1;
        int rightCount = 0;
        int index = 0;
        while (left <= mid && right <= end) {
            if (arr[indexes[right]] < arr[indexes[left]]) {
                tempIndexes[index++] = indexes[right++];
                rightCount++;
            } else {
                tempIndexes[index++] = indexes[left];
                result[indexes[left++]] += rightCount;
            }
        }
        while (left <= mid) {
            tempIndexes[index++] = indexes[left];
            result[indexes[left++]] += rightCount;
        }
        while (right <= end) {
            tempIndexes[index++] = indexes[right++];
        }
        System.arraycopy(tempIndexes, 0, indexes, start, tempIndexes.length);
    }
}

Was this solution helpful?