Python Beginner Algorithms Tutorial

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

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¶

In [1]:
# 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
In [2]:
# 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.

In [23]:
# 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¶

In [24]:
import logging
logging.basicConfig(level=logging.DEBUG, format='%(asctime)-25s %(levelname)-7s %(lineno)-4s %(message)-8s')

In [25]:
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")
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¶

In [26]:
assert smaller_numbers_than_current([8, 1, 2, 2, 3]) ==[4, 0, 1, 1, 3]

2020-03-26 22:00:37,020   DEBUG   3    sorted_list: [1, 2, 2, 3, 8]
2020-03-26 22:00:37,021   DEBUG   5    dictionary: keys are items in input list; values = count of nums smaller than item
2020-03-26 22:00:37,022   DEBUG   7    create variable for running count of nums smaller than item in list
2020-03-26 22:00:37,024   DEBUG   10   1st number in input list will always have 0 elements smaller than it
2020-03-26 22:00:37,026   DEBUG   11   add item: 0 to the dict
2020-03-26 22:00:37,029   DEBUG   14   iterate from index of 1 to length of sorted_list
2020-03-26 22:00:37,030   DEBUG   17   num: 2 & previous_num: 1
2020-03-26 22:00:37,032   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,033   DEBUG   22   this num in iteration is not equal to previous num in sorted_list
2020-03-26 22:00:37,037   DEBUG   23   add key-value pair to dictionary
2020-03-26 22:00:37,038   DEBUG   17   num: 2 & previous_num: 2
2020-03-26 22:00:37,040   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,041   DEBUG   17   num: 3 & previous_num: 2
2020-03-26 22:00:37,041   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,043   DEBUG   22   this num in iteration is not equal to previous num in sorted_list
2020-03-26 22:00:37,044   DEBUG   23   add key-value pair to dictionary
2020-03-26 22:00:37,045   DEBUG   17   num: 8 & previous_num: 3
2020-03-26 22:00:37,048   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,051   DEBUG   22   this num in iteration is not equal to previous num in sorted_list
2020-03-26 22:00:37,052   DEBUG   23   add key-value pair to dictionary
2020-03-26 22:00:37,053   DEBUG   26   dict_count_nums_smaller_than_num: {1: 0, 2: 1, 3: 3, 8: 4}
2020-03-26 22:00:37,054   DEBUG   29   for each item in input list, append dict[item] to output list
2020-03-26 22:00:37,056   DEBUG   32   count of numbers smaller than 8 is 4
2020-03-26 22:00:37,057   DEBUG   32   count of numbers smaller than 1 is 0
2020-03-26 22:00:37,058   DEBUG   32   count of numbers smaller than 2 is 1
2020-03-26 22:00:37,059   DEBUG   32   count of numbers smaller than 2 is 1
2020-03-26 22:00:37,060   DEBUG   32   count of numbers smaller than 3 is 3

In [27]:
assert smaller_numbers_than_current([7, 7, 7, 7]) ==[0, 0, 0, 0]

2020-03-26 22:00:37,070   DEBUG   3    sorted_list: [7, 7, 7, 7]
2020-03-26 22:00:37,071   DEBUG   5    dictionary: keys are items in input list; values = count of nums smaller than item
2020-03-26 22:00:37,071   DEBUG   7    create variable for running count of nums smaller than item in list
2020-03-26 22:00:37,073   DEBUG   10   1st number in input list will always have 0 elements smaller than it
2020-03-26 22:00:37,075   DEBUG   11   add item: 0 to the dict
2020-03-26 22:00:37,076   DEBUG   14   iterate from index of 1 to length of sorted_list
2020-03-26 22:00:37,078   DEBUG   17   num: 7 & previous_num: 7
2020-03-26 22:00:37,079   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,080   DEBUG   17   num: 7 & previous_num: 7
2020-03-26 22:00:37,081   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,083   DEBUG   17   num: 7 & previous_num: 7
2020-03-26 22:00:37,084   DEBUG   18   increment count_nums_smaller by 1
2020-03-26 22:00:37,086   DEBUG   26   dict_count_nums_smaller_than_num: {7: 0}
2020-03-26 22:00:37,087   DEBUG   29   for each item in input list, append dict[item] to output list
2020-03-26 22:00:37,088   DEBUG   32   count of numbers smaller than 7 is 0
2020-03-26 22:00:37,089   DEBUG   32   count of numbers smaller than 7 is 0
2020-03-26 22:00:37,090   DEBUG   32   count of numbers smaller than 7 is 0
2020-03-26 22:00:37,090   DEBUG   32   count of numbers smaller than 7 is 0