Count of Smaller Numbers After Self

Soumya Agrawal
Last Updated: May 13, 2022

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?

If not, then without any ado, let's start with the problem.

 

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.

 

Implementation

class Solution
{
    
  static void countarray(int arr[], int count[], int n)
{
int i, j;

//fill the count array with zeros
for (i = 0; i < n; i++)
count[i]=0;

for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[i])
count[i]++;
}
}
}

// function that prints out an array 
 static void print(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
System.out.print(arr[i] + " ");

System.out.println("");
}

// Main method
public static void main(String[] args)
{

int arr[] = {3,4,2,1,1,2,5,3};
int n = arr.length;
int count[] = new int[n];
countarray(arr, count, n);
print(count, n);
}
}

 

Output

4 5 2 0 0 0 1 0

 

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.

Implementation

public class Solution {

    public int[] Countsmall(int[] nums) {
        int n = nums.Length;
        
        if (n == 0)
            return nums;
        
        int[] counts = new int[n];
        //last node is our root so we can start with next element to left
        Node root = new Node(nums[n-1]);
        
        for (int i = n - 2; i >= 0; i--)
        {
            counts[i] = insert(root, nums[i]);
        }
        
        return counts;
    }
    
    //number of total items that are less than inserted value
    private int insert(Node root, int val) {
        // root is always non-null
        if (val < root.val)
        {
            root.LessCount++;
            if (root.left == null)
            {
                root.left = new Node(val);
                return 0;
            }
            return insert(root.left, val);
        }
        else if (root.val < val)
        {
            if (root.right == null)
            {
                root.right = new Node(val);
                return root.EqCount + root.LessCount;
            }
            return root.EqCount + root.LessCount + Insert(root.right, val);
        }
        else
        {
            root.EqCount++;
            return root.LessCount;
        }
    }
    
    public class Node
    {
        public int val;
        public int EqCount = 1;
        public int LessCount = 0;
        
        public Node left;
        public Node right;
        
        public Node(int val)
        {
            this.val = val;
        }
    }
}

 

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.

 

Implementation

import java.util.*;

public class Solution {

//index and its value pairs
 static class Values {

int val;
int index;

public Values(int val, int index)
{
this.val = val;
this.index = index;
}
}

//To get the count of smaller numbers on right hand side
public static ArrayList<Integer> CountNum(int[] arr)
{

int len = arr.length;
Values[] items = new Values[len];

for (int i = 0; i < len; i++) {
items[i] = new Values(arr[i], i);
}

int[] count = new int[len];
mergeSort(items, 0, len - 1, count);
ArrayList<Integer> res = new ArrayList<>();

for (int i : count) {
res.add(i);
}
return res;
}

//Merge sort
private static void mergeSort(Values[] items,
int low, int high,
int[] count)
{

if (low >= high) {
return;
}

int mid = low + (high - low) / 2;
mergeSort(items, low, mid, count);
mergeSort(items, mid + 1, high, count);
merge(items, low, mid, mid + 1, high, count);
}

//merge the array and count the smaller elements on right side
private static void merge(Values[] items, int low,
int lowEnd, int high,
int highEnd, int[] count)
{
int m = highEnd - low + 1;
Values[] sorted = new Values[m];
int rightCounter = 0;
int lowPtr = low, highPtr = high;
int index = 0;


while (lowPtr <= lowEnd && highPtr <= highEnd) {
if (items[lowPtr].val > items[highPtr].val) {
rightCounter++;
sorted[index++] = items[highPtr++];
}
else {
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}
}

//count of smaller elements when only left array have some element.
while (lowPtr <= lowEnd) {
count[items[lowPtr].index] += rightCounter;
sorted[index++] = items[lowPtr++];
}


//count of smaller elements when only right array have some element.
while (highPtr <= highEnd) {
sorted[index++] = items[highPtr++];
}

System.arraycopy(sorted, 0, items, low, m);
}

//Prints the array
static void print(ArrayList<Integer> countList)
{

for (Integer i : countList)
System.out.print(i + " ");

System.out.println("");
}

// Main function
public static void main(String[] args)
{

int arr[] = { 3,4,2,1,1,2,5,3 };
int n = arr.length;
ArrayList<Integer> countList = CountNum(arr);
print(countList);
}
}

 

Complexity Analysis

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

 

Frequently Asked Questions

  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.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think