# Solution For Count Of Smaller Numbers After Self

The Count of Smaller Numbers After Self problem on LeetCode is a challenging problem that requires you to find the number of elements that are smaller than the current element in an array. In this article, we will provide you with a detailed solution to this problem.

Problem Statement

Given an integer array nums, return an array answer such that answer[i] is the number of smaller elements to the right of nums[i].

Example 1:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is only 1 smaller element (1).
To the right of 1 there is 0 smaller elements.

Approach

We will use the merge-sort approach to find the answer to this problem. The idea behind the merge-sort approach is to divide the array into two halves and count the number of smaller elements in each half separately. Once we have the counts from the left and right half, we merge the two arrays while keeping the order of the elements and updating the count of smaller elements.

Algorithm

1. Create an array res that will store the count of smaller elements for each element in nums.
2. Create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
3. Create an empty list of tuples temp to store the temporary result.
4. Implement a merge-sort algorithm that sorts index_num and tracks the number of elements smaller than the current element in the right half.
5. For each element (index, num) in index_num, add the count of elements in the right half to res[index].

Python Implementation

Here’s the Python implementation of the above algorithm:

“`
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
res = [0]len(nums)
index_num = [(i, nums[i]) for i in range(len(nums))] temp = [0]
len(nums)

``````    def merge_sort(nums, left, right):
if right - left <= 1:
return nums[left:right]
mid = (left + right)//2
left_arr = merge_sort(nums, left, mid)
right_arr = merge_sort(nums, mid, right)
i, j = 0, 0
count = 0
while i < len(left_arr) or j < len(right_arr):
if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
temp[i + j] = left_arr[i]
res[left_arr[i][0]] += count
i += 1
else:
temp[i + j] = right_arr[j]
count += 1
j += 1
return temp[:i+j]

merge_sort(index_num, 0, len(index_num))
return res
``````

“`

Time Complexity: O(n log n)
Space Complexity: O(n)

Let’s understand the implementation step by step.

1. We create an empty list res that will store the count of smaller elements for each element in nums.
`res = [0]*len(nums)`

2. We create a list of tuples index_num that will store the index and number pairs as (index, num) for each element in nums.
`index_num = [(i, nums[i]) for i in range(len(nums))]`

3. We create an empty list of tuples temp to store the temporary result.
`temp = [0]*len(nums)`

4. We implement a merge-sort algorithm to sort index_num and count the number of elements smaller than the current element in the right half.
“`
def merge_sort(nums, left, right):
if right – left <= 1:
return nums[left:right] mid = (left + right)//2
left_arr = merge_sort(nums, left, mid)
right_arr = merge_sort(nums, mid, right)
i, j = 0, 0
count = 0
while i < len(left_arr) or j < len(right_arr):
if j == len(right_arr) or (i < len(left_arr) and left_arr[i][1] <= right_arr[j][1]):
temp[i + j] = left_arr[i] res[left_arr[i][0]] += count
i += 1
else:
temp[i + j] = right_arr[j] count += 1
j += 1
return temp[:i+j]

merge_sort(index_num, 0, len(index_num))
“`

1. For each element (index, num) in index_num, we add the count of elements in the right half to res[index].
`for i, num in index_num: res[i] = res[i] + (len(nums) - 1) - i`

2. Finally, we return res.
`return res`

Conclusion

In this article, we provided a detailed solution to the Count of Smaller Numbers After Self problem on LeetCode. We used the merge-sort approach to divide the array into two halves and count the number of smaller elements in each half separately. Finally, we merged the two arrays while keeping the order of the elements and updating the count of smaller elements. This problem can be solved in O(n log n) time complexity and O(n) space complexity.

## Step by Step Implementation For Count Of Smaller Numbers After Self

```public class Solution {
public List countSmaller(int[] nums) {
List res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
TreeNode root = new TreeNode(nums[nums.length - 1]);
for(int i = nums.length - 2; i >= 0; i--) {
int count = insert(root, nums[i]);
}
Collections.reverse(res);
return res;
}
private int insert(TreeNode root, int val) {
int thisCount = 0;
while(true) {
if(val <= root.val) {
root.count++;
if(root.left == null) {
root.left = new TreeNode(val); break;
} else {
root = root.left;
}
} else {
thisCount += root.count;
if(root.right == null) {
root.right = new TreeNode(val); break;
} else {
root = root.right;
}
}
}
return thisCount;
}
}

class TreeNode {
TreeNode left, right;
int val, count = 1;
public TreeNode(int val) {
this.val = val;
}
}```
```def countSmaller(self, nums):
ans = []
# Sort the array in reverse order
for i in xrange(len(nums)):
# Find the position of current element in the sorted array
pos = bisect.bisect_left(ans, nums[i])
# Insert the current element in the sorted array
ans.insert(pos, nums[i])
# Append the number of elements smaller than the current element to the result
ans.append(pos)
return ans```
```var countSmaller = function(nums) {

// create an empty array to store the results
let results = [];

// iterate through the nums array from the end
for (let i = nums.length - 1; i >= 0; i--) {

// create a counter to keep track of how many smaller numbers there are
let counter = 0;

// iterate through the nums array from the current index to the end
for (let j = i; j < nums.length; j++) {

// if the current number is smaller than the number at index j, increment the counter
if (nums[i] > nums[j]) {
counter++;
}
}

// add the counter to the results array
results.unshift(counter);
}

// return the results array
return results;
};```
```class Solution {
public:
vector countSmaller(vector& nums) {
int n = nums.size();
vector ans(n);
vector t;

for (int i = n - 1; i >= 0; i--) {
int index = getIndex(t, nums[i]);
ans[i] = index;
t.insert(t.begin() + index, nums[i]);
}

return ans;
}
private:
int getIndex(vector &t, int val) {
int n = t.size(), a = 0, b = n - 1;

if (n == 0) return 0;

if (val <= t[a]) return a;
if (val > t[b]) return b + 1;

while (a <= b) {
int c = (a + b) / 2;
if (t[c] >= val) b = c - 1;
else a = c + 1;
}

return a;
}
};```
```public class Solution {
public IList CountSmaller(int[] nums) {
// create an empty list to store the results
IList results = new List();

// edge case: if the input array is empty, return an empty list
if (nums.Length == 0) {
return results;
}

// create a new array that will store the number of smaller elements to the right of each element
int[] smallerCounts = new int[nums.Length];

// create a balanced binary search tree (BST)
BST tree = new BST(nums[nums.Length - 1]);

// starting from the rightmost element in the input array, insert each element into the BST
for (int i = nums.Length - 2; i >= 0; i--) {
// insert the current element into the BST
tree.Insert(nums[i]);

// the number of smaller elements to the right of the current element is equal to the number of elements in the left subtree of the current element's node in the BST
smallerCounts[i] = tree.GetLeftSubtreeSize();
}

// add the number of smaller elements to the right of each element to the results list
foreach (int count in smallerCounts) {
}

return results;
}
}

// Binary Search Tree (BST) node class
public class BSTNode {
public int val;
public int leftSubtreeSize;
public BSTNode left;
public BSTNode right;

public BSTNode(int val) {
this.val = val;
this.leftSubtreeSize = 0;
this.left = null;
this.right = null;
}
}

// Binary Search Tree (BST) class
public class BST {
public BSTNode root;

public BST(int val) {
this.root = new BSTNode(val);
}

// insert a new node into the BST
public void Insert(int val) {
InsertHelper(this.root, val);
}

// helper method to insert a new node into the BST
public void InsertHelper(BSTNode node, int val) {
// if the value to insert is less than the current node's value, insert it into the left subtree
if (val < node.val) {
// if the left subtree is empty, create a new node and insert it
if (node.left == null) {
node.left = new BSTNode(val);
}
// otherwise, recurse on the left subtree
else {
InsertHelper(node.left, val);
}

// increment the size of the left subtree
node.leftSubtreeSize++;
}
// if the value to insert is greater than or equal to the current node's value, insert it into the right subtree
else {
// if the right subtree is empty, create a new node and insert it
if (node.right == null) {
node.right = new BSTNode(val);
}
// otherwise, recurse on the right subtree
else {
InsertHelper(node.right, val);
}
}
}

// get the number of elements in the left subtree
public int GetLeftSubtreeSize() {
return this.root.leftSubtreeSize;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]