Problem

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Examples

Example 1

1
2
3
4
5
6
7
8

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2

1
2

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3

1
2

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

Solution

Method 1 – Counting with Sorting

Intuition

If we sort the array, we can quickly determine how many numbers are smaller than each value by looking at the first index where it appears in the sorted array. This avoids nested loops and speeds up the process.

Approach

  1. Copy and sort the array.
  2. For each unique value, record the first index it appears in the sorted array (this is the count of numbers smaller than it).
  3. For each original number, look up its count from the map.
  4. Return the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> s = nums;
        sort(s.begin(), s.end());
        unordered_map<int, int> m;
        for (int i = 0; i < s.size(); ++i) if (!m.count(s[i])) m[s[i]] = i;
        vector<int> ans;
        for (int x : nums) ans.push_back(m[x]);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func smallerNumbersThanCurrent(nums []int) []int {
    s := append([]int{}, nums...)
    sort.Ints(s)
    m := map[int]int{}
    for i, v := range s {
        if _, ok := m[v]; !ok {
            m[v] = i
        }
    }
    ans := make([]int, len(nums))
    for i, v := range nums {
        ans[i] = m[v]
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] s = nums.clone();
        Arrays.sort(s);
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < s.length; ++i) if (!m.containsKey(s[i])) m.put(s[i], i);
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) ans[i] = m.get(nums[i]);
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun smallerNumbersThanCurrent(nums: IntArray): IntArray {
        val s = nums.sorted()
        val m = mutableMapOf<Int, Int>()
        for ((i, v) in s.withIndex()) if (v !in m) m[v] = i
        return nums.map { m[it]!! }.toIntArray()
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def smallerNumbersThanCurrent(self, nums: list[int]) -> list[int]:
        s = sorted(nums)
        m = {}
        for i, v in enumerate(s):
            if v not in m:
                m[v] = i
        return [m[x] for x in nums]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn smaller_numbers_than_current(nums: Vec<i32>) -> Vec<i32> {
        let mut s = nums.clone();
        s.sort();
        let mut m = std::collections::HashMap::new();
        for (i, &v) in s.iter().enumerate() {
            m.entry(v).or_insert(i);
        }
        nums.iter().map(|&x| *m.get(&x).unwrap() as i32).collect()
    }
}
1
2
3
4
5
6
7
8

class Solution {
    smallerNumbersThanCurrent(nums: number[]): number[] {
        const s = [...nums].sort((a, b) => a - b);
        const m: Record<number, number> = {};
        for (let i = 0; i < s.length; ++i) if (m[s[i]] === undefined) m[s[i]] = i;
        return nums.map(x => m[x]);
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array, where n is the length of nums.
  • 🧺 Space complexity: O(n), for the sorted array and the map.