Table of Contents

# Count of Smaller Numbers After Self – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Given an integer array `nums`

, return* an integer array *`counts`

* where *`counts[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 are2smaller elements (2 and 1). To the right of 2 there is only1smaller element (1). To the right of 6 there is1smaller element (1). To the right of 1 there is0smaller element.

**Example 2:**

Input:nums = [-1]Output:[0]

**Example 3:**

Input:nums = [-1,-1]Output:[0,0]

**Constraints:**

`1 <= nums.length <= 10`

^{5}`-10`

^{4}<= nums[i] <= 10^{4}

# C++ Count of Smaller Numbers After Self LeetCode Solution

```
``````
class Solution {
protected:
void merge_countSmaller(vector<int>& indices, int first, int last,
vector<int>& results, vector<int>& nums) {
int count = last - first;
if (count > 1) {
int step = count / 2;
int mid = first + step;
merge_countSmaller(indices, first, mid, results, nums);
merge_countSmaller(indices, mid, last, results, nums);
vector<int> tmp;
tmp.reserve(count);
int idx1 = first;
int idx2 = mid;
int semicount = 0;
while ((idx1 < mid) || (idx2 < last)) {
if ((idx2 == last) || ((idx1 < mid) &&
(nums[indices[idx1]] <= nums[indices[idx2]]))) {
tmp.push_back(indices[idx1]);
results[indices[idx1]] += semicount;
++idx1;
} else {
tmp.push_back(indices[idx2]);
++semicount;
++idx2;
}
}
move(tmp.begin(), tmp.end(), indices.begin()+first);
}
}
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector<int> results(n, 0);
vector<int> indices(n, 0);
iota(indices.begin(), indices.end(), 0);
merge_countSmaller(indices, 0, n, results, nums);
return results;
}
};
```

# Java Count of Smaller Numbers After Self LeetCode Solution

```
``````
int[] count;
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
count = new int[nums.length];
int[] indexes = new int[nums.length];
for(int i = 0; i < nums.length; i++){
indexes[i] = i;
}
mergesort(nums, indexes, 0, nums.length - 1);
for(int i = 0; i < count.length; i++){
res.add(count[i]);
}
return res;
}
private void mergesort(int[] nums, int[] indexes, int start, int end){
if(end <= start){
return;
}
int mid = (start + end) / 2;
mergesort(nums, indexes, start, mid);
mergesort(nums, indexes, mid + 1, end);
merge(nums, indexes, start, end);
}
private void merge(int[] nums, int[] indexes, int start, int end){
int mid = (start + end) / 2;
int left_index = start;
int right_index = mid+1;
int rightcount = 0;
int[] new_indexes = new int[end - start + 1];
int sort_index = 0;
while(left_index <= mid && right_index <= end){
if(nums[indexes[right_index]] < nums[indexes[left_index]]){
new_indexes[sort_index] = indexes[right_index];
rightcount++;
right_index++;
}else{
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
}
sort_index++;
}
while(left_index <= mid){
new_indexes[sort_index] = indexes[left_index];
count[indexes[left_index]] += rightcount;
left_index++;
sort_index++;
}
while(right_index <= end){
new_indexes[sort_index++] = indexes[right_index++];
}
for(int i = start; i <= end; i++){
indexes[i] = new_indexes[i - start];
}
}
```

# Python 3 Count of Smaller Numbers After Self LeetCode Solution

```
``````
def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
for i in range(len(enum))[::-1]:
if not right or left and left[-1][1] > right[-1][1]:
smaller[left[-1][0]] += len(right)
enum[i] = left.pop()
else:
enum[i] = right.pop()
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1

## Leave a comment below