Problem

This problem was asked by Google.

Given an array of integers, return a new array where each element in the new array is the number of smaller elements to the right of that element in the original input array.

For example, given the array [3, 4, 9, 6, 1], return [1, 1, 2, 1, 0], since:

  • There is 1 smaller element to the right of 3
  • There is 1 smaller element to the right of 4
  • There are 2 smaller elements to the right of 9
  • There is 1 smaller element to the right of 6
  • There are no smaller elements to the right of 1

Code

#!/usr/bin/env python3

arr = [3, 4, 9, 6, 1]

result = {}

for index, value in enumerate(arr):
    if value not in result:
        result[value] = 0
    
    for j in range(index, len(arr)):
        if arr[j] < value:
            result[value] += 1


for key, value in result.items():
    print(f"element = {key} \t count = {value}")

Output:

element = 3 count = 1
element = 4 count = 1
element = 9 count = 2
element = 6 count = 1
element = 1 count = 0