Code Implementation

class Solution:
    def smallerNumbersThanCurrent(self, nums):
        # Sort the array to find the rank of each number
        sorted_nums = sorted(nums)
        # Use a dictionary to store the first occurrence index (count of smaller numbers)
        num_to_count = {}
        for i, num in enumerate(sorted_nums):
            if num not in num_to_count:
                num_to_count[num] = i
        # Build the result using the mapping
        return [num_to_count[num] for num in nums]
      

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> sorted_nums(nums);
        sort(sorted_nums.begin(), sorted_nums.end());
        unordered_map<int, int> num_to_count;
        for (int i = 0; i < sorted_nums.size(); ++i) {
            if (num_to_count.find(sorted_nums[i]) == num_to_count.end()) {
                num_to_count[sorted_nums[i]] = i;
            }
        }
        vector<int> res;
        for (int num : nums) {
            res.push_back(num_to_count[num]);
        }
        return res;
    }
};
      

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        Map<Integer, Integer> numToCount = new HashMap<>();
        for (int i = 0; i < sorted.length; i++) {
            if (!numToCount.containsKey(sorted[i])) {
                numToCount.put(sorted[i], i);
            }
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = numToCount.get(nums[i]);
        }
        return res;
    }
}
      

var smallerNumbersThanCurrent = function(nums) {
    let sorted = [...nums].sort((a, b) => a - b);
    let numToCount = {};
    for (let i = 0; i < sorted.length; i++) {
        if (numToCount[sorted[i]] === undefined) {
            numToCount[sorted[i]] = i;
        }
    }
    return nums.map(num => numToCount[num]);
};
      

Problem Description

Given an array of integers nums, for each element nums[i], determine how many numbers in the array are strictly smaller than nums[i]. The output should be an array where each index i contains the count of numbers in nums that are less than nums[i].

Constraints:

• Each element is compared to all other elements, including itself (but not counted if equal).
• There is exactly one valid answer for each input.
• Elements are not reused for comparison; only strict inequality is considered.

Thought Process

The problem at first seems to require, for every number, a count of how many numbers are less than it. A straightforward way is to use two loops: for each element, scan the entire array and count how many numbers are smaller. However, this brute-force approach has a time complexity of O(n²), which can be slow for larger arrays.

To optimize, we can consider sorting the array. Sorting arranges numbers from smallest to largest, so the position (index) of a number in the sorted array tells us how many numbers are smaller than it. But, since numbers can repeat, we need to be careful to only count the first occurrence of each unique number.

Using a mapping (like a hash map or dictionary), we can store for each unique number its first index in the sorted array. Then, for each original number, we can look up this count efficiently.

Solution Approach

Here’s a step-by-step guide to the optimized solution:

1. Sort the array: Make a sorted copy of nums. Sorting brings all smaller numbers before larger ones.
2. Create a mapping: Use a hash map (dictionary) to map each unique number to its first index in the sorted array. This index represents how many numbers are smaller than that number.
3. Build the result: For each number in the original array, look up its count in the mapping and add it to the result array.

Why use a hash map? Because it allows us to look up the count for each number in constant time, O(1), making the solution efficient.

Summary of steps:

• Sort a copy of the input array.
• Map each unique number to its first appearance index in the sorted array.
• For each number in the original array, retrieve its count from the mapping.

Example Walkthrough

Sample Input: nums = [8, 1, 2, 2, 3]

1. Sort the array: sorted_nums = [1, 2, 2, 3, 8]
2. Build the mapping:
   • First occurrence of 1 is at index 0 → 0 numbers are smaller than 1
   • First occurrence of 2 is at index 1 → 1 number is smaller than 2
   • First occurrence of 3 is at index 3 → 3 numbers are smaller than 3
   • First occurrence of 8 is at index 4 → 4 numbers are smaller than 8

   So the mapping is: {1: 0, 2: 1, 3: 3, 8: 4}

3. Build the result:
   • nums[0] = 8 → 4
   • nums[1] = 1 → 0
   • nums[2] = 2 → 1
   • nums[3] = 2 → 1
   • nums[4] = 3 → 3

   Final Output: [4, 0, 1, 1, 3]

Time and Space Complexity

• Brute-force approach:
  • Time complexity: O(n²) because for each element, we scan the entire array.
  • Space complexity: O(n) for the result array.
• Optimized approach (with sorting and mapping):
  • Time complexity: O(n log n) due to sorting. Mapping and building the result are both O(n).
  • Space complexity: O(n) for the sorted array, mapping, and result array.

The optimized approach is much faster for larger arrays because it avoids the nested loop.

Summary

The key insight is that sorting the array reveals, for each number, how many numbers are smaller than it by its position in the sorted array. By mapping each unique number to its first occurrence index in the sorted array, we can quickly look up the answer for each element in the original array. This approach is both simple and efficient, making it an elegant solution to the problem.