315. Count of Smaller Numbers After Self

Problem Statement

Count of Smaller Numbers After Self - LeetCode

Pattern: Merge Sort

---

Naive Solution

public List<Integer> countSmaller1(int[] nums) {
	ArrayList<Integer> res = new ArrayList<>();
	for (int i = 0; i < nums.length; i++) {
		int count = 0;
		for (int j = i + 1; j < nums.length; j++)
			if (nums[j] < nums[i]) count++;
		res.add(count);
	}
	return res;
}

For every element count no. of elements to its right smaller thant it. that is the inverstion count of that number.

Optimised Solution

private class IndexedInteger {
	int val;
	int originalIdx;
	
	public IndexedInteger(int val, int originalIdx) {
		this.val = val;
		this.originalIdx = originalIdx;
	}
}
 
public List<Integer> countSmaller(int[] nums) {
	// create numsList to keep track of original index
	IndexedInteger[] numsList = new IndexedInteger[nums.length];
	for (int i = 0; i < nums.length; i++) numsList[i] = new IndexedInteger(nums[i], i);
	
	// find and store Inversion count for numbers in numsList in res using their original index
	int[] res = new int[nums.length];
	mergeSort(numsList, 0, nums.length - 1, res);
	
	// convert to arrayList and return
	ArrayList<Integer> result = new ArrayList<>();
	for (int num : res) result.add(num);
	return result;
}
 
private void mergeSort(IndexedInteger[] numsList, int start, int end, int[] res) {
	// single element exit condition
	if (start >= end) return;
	
	// find mid
	int mid = start + (end - start) / 2;
	
	// recurse for left and right subarray
	mergeSort(numsList, start, mid, res);
	mergeSort(numsList, mid + 1, end, res);
	
	merge(numsList, start, end, res);
}
 
private void merge (IndexedInteger[] numsList, int start, int end, int[] res) {
	// temp LL to store merged/sorted arr
	LinkedList<IndexedInteger> temp = new LinkedList<>();
	
	// left & right subarray pointers, inversionCount -> count of smaller els in right subarr
	int mid = start + (end - start) / 2, left = start, right = mid + 1, inversionCount = 0;
	
	// merge subarrs into temp
	while (left <= mid && right <= end) {
		// left is (strictly) smaller (not equal to)
		if (numsList[right].val < numsList[left].val) {
			inversionCount++;                   // increment inversion count
			temp.add(numsList[right++]);
		}
		// right is smaller
		else {
			res[numsList[left].originalIdx] += inversionCount;    // update res inversionCount
			temp.add(numsList[left++]);
		}
	}
	
	// merge leftovers
	while (left <= mid) {
		res[numsList[left].originalIdx] += inversionCount;
		temp.add(numsList[left++]);
	}
	while (right <= end) {
		temp.add(numsList[right++]);
	}
	
	// update sorted array in numsList
	for (IndexedInteger t : temp) numsList[start++] = t;
}

• we update inversion count, only when right is smaller, since only then it would be called an inversion, else it would just be an equal element to the right of the same element, it wouldnt count as an inversion
• we have a temp array

Related: Count Inversions | Practice | GeeksforGeeks