Here, We see Count of Smaller Numbers After Self LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
![Count of Smaller Numbers After Self LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Count of Smaller Numbers After Self LeetCode Solution
Table of Contents
Problem Statement
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]
Count of Smaller Numbers After Self LeetCode Solution C++
class Solution {
public:
void merge(int left, int mid, int right, vector<pair<int, int>>& arr,vector<int>& count)
{
vector<pair<int, int>> temp(right - left + 1);
int i = left;
int j = mid + 1;
int k = 0;
while(i <= mid && j <= right)
{
if(arr[i].first <= arr[j].first)
{
temp[k++] = arr[j++];
}
else
{
count[arr[i].second] += (right - j + 1);
temp[k++] = arr[i++];
}
}
while(i <= mid)
{
temp[k++] = arr[i++];
}
while(j <= right)
{
temp[k++] = arr[j++];
}
for(int l = left; l <= right; l++)
arr[l] = temp[l - left];
}
void mergeSort(int left, int right, vector<pair<int, int>>& arr, vector<int>& count)
{
if(left >= right)
{
return;
}
int mid = left + (right - left) / 2;
mergeSort(left, mid, arr, count);
mergeSort(mid + 1, right, arr, count);
merge(left, mid, right, arr, count);
}
vector<int> countSmaller(vector<int>& nums) {
int n=nums.size();
vector<pair<int, int>> arr;
for(int i = 0; i < n; i++)
{
arr.push_back({nums[i], i});
}
vector<int> count(n, 0);
mergeSort(0, n - 1, arr, count);
return count;
}
};
Code language: JavaScript (javascript)
Count of Smaller Numbers After Self LeetCode Solution Java
class Solution {
class Node {
Node left, right;
int val, sum, dup = 1;
public Node(int v, int s) {
val = v;
sum = s;
}
}
public List<Integer> countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
Node root = null;
for (int i = nums.length - 1; i >= 0; i--) {
root = insert(nums[i], root, ans, i, 0);
}
return Arrays.asList(ans);
}
private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
if (node == null) {
node = new Node(num, 0);
ans[i] = preSum;
} else if (node.val == num) {
node.dup++;
ans[i] = preSum + node.sum;
} else if (node.val > num) {
node.sum++;
node.left = insert(num, node.left, ans, i, preSum);
} else {
node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
}
return node;
}
}
Code language: PHP (php)
Count of Smaller Numbers After Self Solution JavaScript
var countSmaller = function(nums) {
let sorted = [], result = [];
for (let i=nums.length-1;i>=0;i--) {
let left = 0, right = sorted.length;
while(left < right) {
let mid = left + Math.floor((right-left)/2);
if (nums[i] > sorted[mid]) {
left = mid + 1;
} else {
right = mid;
}
}
result.unshift(left);
sorted.splice(left, 0, nums[i]);
}
return result;
}
Code language: JavaScript (javascript)
Count of Smaller Numbers After Self Solution Python
class Solution(object):
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