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

Date published: 2020-04-07

Category: Python

Subcategory: Beginner Algorithms

Tags: 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¶

In [1]:

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

# 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]

# 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

# 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')

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")
            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

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¶

In [26]:

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

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]

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