Program to return number of smaller elements at right of the given list in Python

In Python, a list is a ordered and mutable data structure where elements are enclosed in square braces []. In some scenarios, we may need to count how many elements to the right of each element in the list are smaller than it.

Using Binary Search with bisect_left() Function

The bisect_left() Function of the bisect method is used locate the insertion point for an element in a sorted list to maintain the list's sorted order. The insertion point returned by bisect_left() is the index where the element can be inserted without violating the sort order by placing it before any existing entries with the same value.

Example-1

Following is the example in which we go through the input list from right to left by using the bisect_left() function to insert elements into a sorted list by tracking the position of insertion, which represents the count of smaller elements -

import bisect def count_smaller_elements(arr): result = [] sorted_list = [] for num in reversed(arr): index = bisect.bisect_left(sorted_list, num) result.append(index) bisect.insort(sorted_list, num) return result[::-1] # Sample input list numbers = [5, 2, 6, 1] print("Count of smaller elements to the right:", count_smaller_elements(numbers)) 

Here is the output of the above example -

Count of smaller elements to the right: [2, 1, 1, 0] 

Example-2

Here is another example to return number of smaller elements at right of the given list in python using the bisect_left() function of the bisect module -

import bisect class Solution: def solve(self, nums): res, inc = [], [] while nums: num = nums.pop() res.append(bisect.bisect_left(inc, num)) bisect.insort(inc, num) return res[::-1] ob = Solution() nums = [4, 5, 9, 7, 2] print(ob.solve(nums)) 

Below is the output of the above example -

[1, 1, 2, 1, 0]