# How Many Numbers Are Smaller Than the Current Number (via Leetcode)

- April 7, 2020
- Key Terms: functions, loops, lists, dictionaries

This problem can be found on Leetcode.

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.

#### Test Cases¶

```
# assert smaller_numbers_than_current([8, 1, 2, 2, 3]) ==[4, 0, 1, 1, 3]
```

In the test case above, here is my reasoning for the solution:

index in input list | number | numbers in list smaller than number | count numbers in list smaller than number |
---|---|---|---|

0 | 8 | [1, 2, 2, 3] | 4 |

1 | 1 | [ ] | 0 |

2 | 2 | [1] | 1 |

3 | 2 | [1] | 1 |

4 | 3 | [1, 2, 2] | 3 |

```
# assert smaller_numbers_than_current([7, 7, 7, 7]) ==[0, 0, 0, 0]
```

In the test case above, here is my reasoning for the solution:

index in input list | number | numbers in list smaller than number | count numbers in list smaller than number |
---|---|---|---|

0 | 7 | [ ] | 0 |

1 | 7 | [ ] | 0 |

2 | 7 | [ ] | 0 |

3 | 7 | [ ] | 0 |

### Pseudocode¶

This pseudocode doesn't cover every detail - but most of the high-level logic.

```
# create a function that takes in a list of numeric values
# created sorted list
# iterate over item in sorted list
# make dictionary with keys as item and value as count of items smaller than it
# create empty output_list
# iterate over each item in input list
# look up in the item as a key in the dictionary and add value to output_list
```

Let `n`

be the length of items in the input list.

The sorted list will hold `n`

values and so space complexity is O(n). The dictionary can hold up to `n`

unique values which in the worst case scenario is `n`

; space complexity is O(n). Total space complexity is O(n) + O(n) which is O(2n).

Time complexity to create a sorted list is O(nlogn). Iteration over the sorted list is O(n). Iteration over the input list is O(n). Therefore, total time complexity is O(2n) + O(nlogn).

### Code¶

```
import logging
logging.basicConfig(level=logging.DEBUG, format='%(asctime)-25s %(levelname)-7s %(lineno)-4s %(message)-8s')
```

```
def smaller_numbers_than_current(input_list):
sorted_list = sorted(input_list)
logging.debug(f"sorted_list: {sorted_list}")
logging.debug("dictionary: keys are items in input list; values = count of nums smaller than item")
dict_count_nums_smaller_than_num = {}
logging.debug("create variable for running count of nums smaller than item in list")
count_nums_smaller = 0
logging.debug("1st number in input list will always have 0 elements smaller than it")
logging.debug("add item: 0 to the dict")
dict_count_nums_smaller_than_num[sorted_list[0]] = count_nums_smaller
logging.debug("iterate from index of 1 to length of sorted_list")
for index in range(1, len(sorted_list)):
logging.debug(f"num: {sorted_list[index]} & previous_num: {sorted_list[index-1]}")
logging.debug("increment count_nums_smaller by 1")
count_nums_smaller += 1
if sorted_list[index] != sorted_list[index-1]:
logging.debug("this num in iteration is not equal to previous num in sorted_list")
logging.debug("add key-value pair to dictionary")
dict_count_nums_smaller_than_num[sorted_list[index]] = count_nums_smaller
logging.debug(f"dict_count_nums_smaller_than_num: {dict_count_nums_smaller_than_num}")
output_list = []
logging.debug("for each item in input list, append dict[item] to output list")
for item in input_list:
count_nums_smaller = dict_count_nums_smaller_than_num[item]
logging.debug(f"count of numbers smaller than {item} is {count_nums_smaller}")
output_list.append(count_nums_smaller)
return output_list
```

### Validate Code with Test Cases¶

```
assert smaller_numbers_than_current([8, 1, 2, 2, 3]) ==[4, 0, 1, 1, 3]
```

```
assert smaller_numbers_than_current([7, 7, 7, 7]) ==[0, 0, 0, 0]
```