class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int count = 0;
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i ++) {
            count = 0;
            
           for (int j = 0; j < nums.length; j ++) {
                if (j != i && nums[j] < nums[i]) {
                    count++ ;
                }
            }
            
            result[i] = count;
        }
        return result;
        
    }
}

public int[] smallerNumbersThanCurrent4(int[] nums) {
	int size = nums.length;

	Map<Integer, List<Integer>> map = new HashMap<>();

	// O(n)
	for (int i = 0; i < size; i++)
		if (map.containsKey(nums[i]))
			map.get(nums[i]).add(i);
		else
			map.put(nums[i], new ArrayList<>(Arrays.asList(i)));

    // O(nlgn)
	Arrays.sort(nums);
	
	// O(n)
	int[] count = new int[size];
	for (int i = 0; i < size;) {
		int j = i;
		for (int index : map.get(nums[i])) {
			count[index] = j;
			i++;
		}
	}
	return count;
}

//Same method but with streams
public int[] smallerNumbersThanCurrent(int[] nums) {
	int size = nums.length;
	// O(n)
	Map<Integer, List<Integer>> map = IntStream.range(0, size)
											   .boxed()
											   .collect(Collectors.groupingBy(i -> nums[i]));
	// O(nlgn)
	Arrays.sort(nums);
	
	// O(n)
	int[] count = new int[size];
	for (int i = 0; i < size;) {
		int j = i;
		for (int index : map.get(nums[i])) {
			count[index] = j;
			i++;
		}
	}
	return count;
}

/*
Time optimised through sort: T: O(nlg n), S: O(n)

Idea here is to build a map of numbers to their list of occurences. 
list because duplicates are allowed. 
This map will be used to fill the result array.
Sort the original array (nums) in ascending order. 
Now every number to the left of the current number is <= to it.
Iterate from 0 to size - 1. 
The current index will give the number count which is/are 
less than the current number in sorted array. 
Populate the result array with the index-copy.
To handle duplicates, 
increment i (index) when iterating through the list of
occurences to move the pointer one step forward. 
This ensures that same duplicates get the same result 
i.e. same numer of numbers smaller than them 
because this count will be the same for all occurences 
of that number. e.g. if 3 numbers are less than n, 
then result for all occurences will be 3.

*/