304 North Cardinal St.
Dorchester Center, MA 02124

# Count of Smaller Numbers After Self LeetCode Solution

## Problem – Count of Smaller Numbers After Self

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 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 1 smaller element (1).
To the right of 1 there is 0 smaller element.``````

Example 2:

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

Example 3:

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

Constraints:

• `1 <= nums.length <= 105`
• `-104 <= nums[i] <= 104`

### Count of Smaller Numbers After Self LeetCode Solution in Java

``````    // Wrapper class for each and every value of the input array,
// to store the original index position of each value, before we merge sort the array
private class ArrayValWithOrigIdx {
int val;
int originalIdx;

public ArrayValWithOrigIdx(int val, int originalIdx) {
this.val = val;
this.originalIdx = originalIdx;
}
}

public List<Integer> countSmaller(int[] nums) {
if (nums == null || nums.length == 0) return new LinkedList<Integer>();
int n = nums.length;
int[] result = new int[n];

ArrayValWithOrigIdx[] newNums = new ArrayValWithOrigIdx[n];
for (int i = 0; i < n; ++i) newNums[i] = new ArrayValWithOrigIdx(nums[i], i);

mergeSortAndCount(newNums, 0, n - 1, result);

// notice we don't care about the sorted array after merge sort finishes.
// we only wanted the result counts, generated by running merge sort
for (int i : result) resultList.add(i);
return resultList;
}

private void mergeSortAndCount(ArrayValWithOrigIdx[] nums, int start, int end, int[] result) {
if (start >= end) return;

int mid = (start + end) / 2;
mergeSortAndCount(nums, start, mid, result);
mergeSortAndCount(nums, mid + 1, end, result);

// left subarray start...mid
// right subarray mid+1...end
int leftPos = start;
int rightPos = mid + 1;
int numElemsRightArrayLessThanLeftArray = 0;
while (leftPos < mid + 1 && rightPos <= end) {
if (nums[leftPos].val > nums[rightPos].val) {
// this code block is exactly what the problem is asking us for:
// a number from the right side of the original input array, is smaller
// than a number from the left side
//
// within this code block,
// nums[rightPos] is smaller than the start of the left sub-array.
// Since left sub-array is already sorted,
// nums[rightPos] must also be smaller than the entire remaining left sub-array
++numElemsRightArrayLessThanLeftArray;

// continue with normal merge sort, merge
++rightPos;
} else {
// a number from left side of array, is smaller than a number from
// right side of array
result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

// Continue with normal merge sort
++leftPos;
}
}

// part of normal merge sort, if either left or right sub-array is not empty,
// move all remaining elements into merged result
while (leftPos < mid + 1) {
result[nums[leftPos].originalIdx] += numElemsRightArrayLessThanLeftArray;

++leftPos;
}
while (rightPos <= end) {
++rightPos;
}

// part of normal merge sort
// copy back merged result into array
int pos = start;
for (ArrayValWithOrigIdx m : merged) {
nums[pos] = m;
++pos;
}
}
``````

### Count of Smaller Numbers After Self LeetCode Solution in Python

``````def countSmaller(self, nums):
def sort(enum):
half = len(enum) / 2
if half:
left, right = sort(enum[:half]), sort(enum[half:])
m, n = len(left), len(right)
i = j = 0
while i < m or j < n:
if j == n or i < m and left[i][1] <= right[j][1]:
enum[i+j] = left[i]
smaller[left[i][0]] += j
i += 1
else:
enum[i+j] = right[j]
j += 1
return enum
smaller = [0] * len(nums)
sort(list(enumerate(nums)))
return smaller``````

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

``````    #define iterator vector<vector<int>>::iterator
void sort_count(iterator l, iterator r, vector<int>& count) {
if (r - l <= 1) return;
iterator m = l + (r - l) / 2;
sort_count(l, m, count);
sort_count(m, r, count);
for (iterator i = l, j = m; i < m; i++) {
while (j < r && (*i)[0] > (*j)[0]) j++;
count[(*i)[1]] += j - m; // add the number of valid "j"s to the indices of *i
}
inplace_merge(l, m, r);
}
vector<int> countSmaller(vector<int>& nums) {
vector<vector<int>> hold;
int n = nums.size();
for (int i = 0; i < n; ++i) hold.push_back(vector<int>({nums[i], i})); // "zip" the nums with their indices
vector<int> count(n, 0);
sort_count(hold.begin(), hold.end(), count);
return count;
}
``````
##### Count of Smaller Numbers After Self LeetCode Solution Review:

In our experience, we suggest you solve this Count of Smaller Numbers After Self LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Count of Smaller Numbers After Self LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Count of Smaller Numbers After Self LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions