LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

The problem can be found here.
The obvious brute force solution to has a complexity of O(n^2), so we should try to think of something better. I present my solution below.

Solution explanation

After we sort the array, the index of an element shows how many smaller elements there are, except when we encounter duplicate elements. To fix this, we scan the array, and if the current number is seen for the first time (meaning that all elements before it are smaller, and none are equal to it), we add the index to the dictionary, otherwise we skip it, because even though the index is incremented, the previous number is equal to the current one, not smaller.

Afterwards, we simply scan the original array (so that we can output the answers in the correct order), and retrieve the quantities for each of the elements.

Complexity

The Array.Sort() method has an average case complexity of O(n*logn), copying the array and scanning the elements takes up O(n).

Code

public class Solution {
    public int[] SmallerNumbersThanCurrent(int[] nums) {
        Dictionary<int, int> smallerNumbers = new Dictionary<int, int>();  
        int[] numsOriginal = new int[nums.Length];
        int[] ans = new int[nums.Length];

        // Copy original array
        for(int k = 0; k < nums.Length; k++)    
            numsOriginal[k] = nums[k];

        Array.Sort(nums);

        // First element has no smaller numbers anyway
        smallerNumbers.TryAdd(nums[0], 0);

        for(int i = 1; i < nums.Length; i++) 
            if(nums[i - 1] != nums[i])
                smallerNumbers.TryAdd(nums[i], i);

        for(int j = 0; j < numsOriginal.Length; j++)
            if(smallerNumbers.ContainsKey(numsOriginal[j]))
                ans[j] = smallerNumbers[numsOriginal[j]];

        return ans;
    }
}