1365. How Many Numbers Are Smaller Than the Current Number

Problem Statement

Pattern:

---

Solution

// freq array prefix sum O(n)
public int[] smallerNumbersThanCurrent(int[] nums) {
	// this method is viable since nums[i] < 100
	final int MAX = 101;
	//create freq arr
	int[] freq = new int[MAX];
	for (int i = 0; i < nums.length; i++) {
		freq[nums[i]]++;
	}
	
	// convert into prefix sum arr
	for (int i = 1; i < MAX; i++) {
		// each index stores the no of elements smaller than it
		freq[i] += freq[i - 1];
	}
	
	// write to nums array
	for (int i = 0; i < nums.length; i++) {
		// already correct/ avoid out of bounds
		if(nums[i] == 0) break; 
		nums[i] = freq[nums[i] - 1];  // freq of nums 'up to' nums[i]
	}
	return nums;
}
 
// sort array O(nlogn)
public int[] smallerNumberThanCurrentSort(int[] nums) {
	// create sorted array
	int [] sortedNums = nums.clone();
	Arrays.sort(sortedNums);
	
	// insert first location
	HashMap<Integer, Integer> map = new HashMap<>();
	for (int i = 0; i < sortedNums.length; i++)
		// insert the first pos of el in sorted array
		map.putIfAbsent(sortedNums[i], i);
	
	// rewrite array
	for (int i = 0; i < nums.length; i++)
		nums[i] = map.get(nums[i]);
	
	return nums;
}

Notes

• 2 ways to do it
• Both find the number of elements before the current element
  • Enter freqs into a freq array
  • Convert into prefix sum
    • freq[i] gives you the number of elements that exist in array till value i in nums (including i).
    • So to find no. of elements till value i not including i , get freq[i-1]
• Hashmap implmentation stores the first 0-based index of every element’s first occurrence if the array was sorted
  • That gives you the no. of elements smaller nums[i],
  • dry run with first element 1