# Count of Smaller Numbers After Self

## Introduction

In companies like Microsoft and Amazon, a common question in the coding interview is the count of smaller numbers after self. It is solved using one of the exciting topics: Binary Search tree(BST), Segment Tree, Merge Sort Algorithm.

Do you know how to solve this problem of the count of smaller numbers?

## Problem Statement

Before heading on to the solution, let me briefly introduce this problem to understand it better.

You will be given an array consisting of integers in which for every integer, you have to count the number of integers smaller than it on the right-hand side and store the count in a count array.

Count array will give you the number of smaller numbers.

For example: • Integers to the right of '3', there are 4 smaller integers.
• Integers to the right of '4', there are 5 smaller integers.
• Integers to the right of '2', there are 2 smaller integers.
• Integers to the right of '1', there are 0 smaller integers.
• Integers to the right of '1', there are 0 smaller integers.
• Integers to the right of '2', there are 0 smaller integers.
• Integers to the right of '5', there are 1 smaller integer.
• Integers to the right of '3', there are 0 smaller integers.

Now we know what problem we have to deal with, we will look into different methods of solving it.

We will first head with a naive or straightforward approach to solving this problem then move on to the efficient methods by keeping the complexities in mind.

Note: Please try to solve the Count of Smaller Numbers After Self on CodeStudio before stepping into the solution

## Approach 1: Brute Force

By brute force approach means the most simple or first thought comes to our mind. In this approach, we didn't care about the time complexity.

• Here we will be using two loops.
• An outer loop will be used for picking up the elements from the left to the right.
• The inner loop will iterate through the right-hand side elements of the picked element and increment the count.
• Count of all the elements is stored in the new array.

Output

### Analysis of Complexity

• Time Complexity: The time complexity will be O(n^2).Where n is given as the length of the array.
• Space Complexity: The space complexity is O(1).

## Approach 2: Binary Search Tree

The following approach we will be using to solve this problem is Binary Search Tree. Let's see how BST can help us to solve this problem efficiently.

### Algorithm

• Here at each node, we will store two variables. One variable will be accounted for the duplicate elements, and the other will be the number of elements on the left subtree.
• The number we require would be returned by our recursive procedure, which is the number of elements less than the inserted element.
• We should delete the right subtree if we go left at a specific step because all elements on the right are greater than the root, and root is greater than the current element. We return the result of the recursive algorithm for the left subtree.
• We should delete the right subtree if we go left at a specific step because all elements on the right are greater than the root, and root is greater than the current element. We return the result of the recursive algorithm for the left subtree.
• Also, we need to add recursively whatever the function returns for the right element to the root, as we don't know where the element will be placed in the right subtree.
• Now, if we find an element equal to the current element, we must return its left subtree.
• Count of smaller numbers can be found in this way.

Let's proceed towards the code if the algorithm is clear.

### Complexity Analysis

Time Complexity: The time complexity is O(nlogn).

Space Complexity: The space complexity will be O(1).

## Approach 3: Merge Sort

The idea we will be using is a Merge sort while merging two arrays. It is a divide and conquers technique. It divides the array into two parts, and makes a call to itself for the two halves, and merges it. You can gain more information about this algorithm on CodeStudio.

Here when the higher index element is less than the lower index element, it shows that the higher index element is smaller than all the elements after that lower index as the left part will be already sorted.

Finally, add up all the elements after the lower index element for the required count.

### Complexity Analysis

• Time complexity: The Time complexity is O(nlogn).
• Space complexity: The space complexity is O(n).

1. What do you mean by Binary Search Tree?
Answer: A binary search tree is a data structure in which a node's left subtree contains only those whose keys have a lesser value than the node's key.
The node's right subtree contains only those whose keys have greater value than the node's key. The left and right subtree each must also be a binary search tree.

2. What is the Merge Sort Algorithm?
Answer: Merge sort is a Divide and conquer algorithm. It divides the array into two halves, makes a call to itself, and then merges the two sorted halves.

3. What are the best approaches to solve this problem?
Answer: There can be more approaches to solve this problem. One of the approaches is Segment Tree, AVL Tree, and many more. Count of smaller numbers is efficiently solved using these techniques.

## Key Takeaways

In this blog, we discuss the problem's solution, where we need to print the array, consisting of the counts of every integer smaller than the picked integer on the right-hand side.

We see three approaches to find the count of smaller numbers, coded in Java language. Apart from this, you can practice more questions similar to this Count of Range Sum, How Many Numbers Are Smaller Than the Current Number and many more.

You can also have a view of the Data Structures and Algorithms-guided path to start your preparation from scratch. 