Count of Smaller Numbers After Self

This page explains Java solution to problem `Count of Smaller Numbers After Self` using `Merge Sorting` algorithm.

Problem Statement

You are given an integer array `nums` and you have to return a new counts array. The counts array has the property where `counts[i]` is the number of smaller elements to the right of `nums[i]`.

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

class CountOfSmallerNumbersAfterSelf {
public List<Integer> countSmaller(int[] arr) {
if(arr.length == 0) return new ArrayList<Integer>();
Integer[] res = new Integer[arr.length];
int[][] indexedArray = new int[arr.length][2];
for(int i = 0; i < arr.length; i++) {
indexedArray[i][0] = arr[i];
indexedArray[i][1] = i;
res[i] = 0;
}
mergeSort(indexedArray, res);
return Arrays.asList(res);
}

private int[][] mergeSort(int[][] arr, Integer[] res) {
int lo = 0;
int hi = arr.length - 1;
int mid = lo + (hi - lo) / 2;

if(lo == hi) return arr;

int[][] left = mergeSort(slice(arr, lo, mid), res);
int[][] right = mergeSort(slice(arr, mid + 1, hi), res);
int l = 0;
int r = 0;
int leftCount = 0;

int[][] out = new int[arr.length][2];
int index = 0;
while(l < left.length && r < right.length) {
if(left[l][0] > right[r][0]) {
out[index++] = right[r++];
leftCount++;
}
else {
out[index++] = left[l];
int resIndex = left[l++][1];
res[resIndex] += leftCount;
}
}
while(l < left.length) {
out[index++] = left[l];
int resIndex = left[l++][1];
res[resIndex] += leftCount;
}
while(r < right.length) {
out[index++] = right[r++];
leftCount++;
}
return out;
}

private int[][] slice(int[][] arr, int from, int to) {
int[][] res = new int[to - from + 1][2];
int index = 0;
for(int i = from; i <= to; i++) {
res[index++] = arr[i];
}
return res;
}
}

``````

Time Complexity

O(N * log N) Where
N is total number of elements in an input array

O(N)