tags: leetcode easy Array Hash Table Sorting Counting

1365. How Many Numbers Are Smaller Than the Current Number

Description

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:

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:

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

Example 3:

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

Constraints:

• $2 \leq nums.length \leq 500$
• $0 \leq nums[i] \leq 100$

Code

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {
    int* returnNums = calloc(numsSize, sizeof(int));
    int i, count[101] = { 0 }, all[101] = { 0 };
    for (i = 0; i < numsSize; i++)
        count[nums[i]]++;
    all[1] = count[0];
    for (i = 1; i <= 100; i++)
        all[i] = count[i - 1] + all[i - 1];
    for (i = 0; i < numsSize; i++)
        returnNums[i] = all[nums[i]];
    *returnSize = numsSize;
    return returnNums;
}

Complexity

Space	Time
$O(N)$	$O(N)$

Result

• Runtime : 18 ms, 89.38%
• Memory usage : 6.7 MB, 94.14%