# 315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Input: [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.
# Solution
Approach 1: O(NlogN)
merge sort. Count the number of nums swapped from the right side to the left during the merge step.
Approach 2: O(NlogN)
to O(N^2)
binary search tree. Insert numbers from the back, use bst's property: inorder traversal yields a sorted array.
Approach 3: O(NlogN)
binary index tree on frequency array of ranked nums.
# Code (Python)
Approach 1:
def countSmaller(self, nums: List[int]) -> List[int]:
# O(NlogN) merge sort idea: count the number of nums swapped from the right side to the left during the merge step
if not nums:
return []
counts = [0 for _ in range(len(nums))]
# [(index0, value0), ...] to remember its original index
self._mergesort(list(enumerate(nums)), counts)
return counts
def _mergesort(self, nums, counts):
# returns a new array -- mergesort is not an inplace sort
if len(nums) == 1:
return nums
left_part = self._mergesort(nums[:len(nums)//2], counts)
right_part = self._mergesort(nums[len(nums)//2:], counts)
# use two pointers to merge two parts into nums
l, r = 0, 0
while l < len(left_part) or r < len(right_part):
# every time we put in something on the left part, account how many elements on the right went before it. things on the right don't have to do this because we only count nums jumped from right to the left
if r == len(right_part) or (l < len(left_part) and left_part[l][1] <= right_part[r][1]): # left_part[l][1] <= because we put left first to avoid a swap
nums[r+l] = left_part[l]
counts[left_part[l][0]] += r
l += 1
else:
nums[r+l] = right_part[r]
r += 1
return nums
# OR can also go backwards in the merge
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]: # can also go backwards here
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
Approach 2:
class TreeNode:
def __init__(self, val):
self.left_nodes = 0 # num of elements(including repetitions) in left subtree -- meaning all nums less than it in the bst
self.rep = 1 # num of repetitions of this value
self.val = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
# returns num of nodes whose values are smaller than self
if not self.root:
self.root = TreeNode(value)
return 0
node = self.root
num_smaller = 0
# iteratively add a node into the bst
while node:
if value < node.val:
node.left_nodes += 1
if not node.left:
node.left = TreeNode(value)
return num_smaller
node = node.left
elif value > node.val:
num_smaller += node.rep + node.left_nodes
if not node.right:
node.right = TreeNode(value)
return num_smaller
node = node.right
else: # value == node.val
node.rep += 1
num_smaller += node.left_nodes
return num_smaller
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
if not nums:
return []
if len(nums) == 1:
return [0]
counts = [0] * len(nums)
bst = BinarySearchTree()
for i in range(len(nums) - 1, -1, -1):
counts[i] = bst.insert(nums[i])
return counts
Approach 3:
class BinaryIndexTree:
def __init__(self, n):
self._sums = [0] * (n + 1) # valid parts from 1 to n + 1, because you can't get lowbits of 0
def update(self, delta, index):
while index < len(self._sums):
self._sums[index] += delta
# increament the lowest bit for a number, e.g. lowbit(10110) = 10
# - (10110) = 01001 + 1 = 10010
index += (index & -index)
def query(self, index):
result = 0
while index > 0:
result += self._sums[index]
index -= (index & -index)
return result
class Solution:
def countSmaller(self, nums: List[int]) -> List[int]:
# think of a frequency array, where index of array correspond to the value of the num
# put nums from the back to front into the frequency array, result for each number is the sum(freq_array[:num-1])
# that's prefix sum with changing values -- use Binary Index Tree: https://www.youtube.com/watch?v=WbafSgetDDk
# the values of nums can be "compressed" into just a ranks so that the freq array don't have to be that sparse
ranks = {}
for i, num in enumerate(sorted(nums)):
if i == 0:
ranks[num] = 1 # rank starts from 1
else:
if num != prev_num:
ranks[num] = ranks[prev_num] + 1
prev_num = num
tree = BinaryIndexTree(len(nums))
result = [0] * len(nums)
for i, num in enumerate(nums[::-1]):
value = ranks[num]
tree.update(1, value)
result[i] = tree.query(value - 1)
return result[::-1]
# Code (C++)
Approach 1:
// Merge sort.
class Solution {
private:
vector<int> res;
vector<int> oriToNew;
vector<int> newToOri;
void goMergeSort(vector<int>& nums, int head, int tail) {
if (head >= tail)
return;
int mid = head + (tail - head) / 2;
// Merge sort for sub arrays.
goMergeSort(nums, head, mid);
goMergeSort(nums, mid+1, tail);
// Merge sort.
vector<int> tmp;
int i1 = head;
int i2 = mid + 1;
int offset = 0;
while (i1 <= mid || i2 <= tail)
{
if (i2 > tail || i1 <= mid && nums[i1] <= nums[i2])
{
tmp.push_back(nums[i1]);
oriToNew[newToOri[i1]] = head + tmp.size() - 1;
res[newToOri[i1]] += offset;
i1++;
}
else
{
tmp.push_back(nums[i2]);
oriToNew[newToOri[i2]] = head + tmp.size() - 1;
i2++;
offset++;
}
}
for (int i = head; i <= tail; ++i)
{
nums[i] = tmp[i-head];
newToOri[oriToNew[i]] = i;
}
}
public:
vector<int> countSmaller(vector<int>& nums) {
for (int i = 0; i < nums.size(); ++i)
{
oriToNew.push_back(i);
newToOri.push_back(i);
res.push_back(0);
}
goMergeSort(nums, 0, nums.size()-1);
return res;
}
};
Approach 2:
// Binary search tree (BST).
class Solution {
struct TreeNode {
int val;
int dupNum;
int leftNum;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), dupNum(1), leftNum(0), left(NULL), right(NULL) {}
};
private:
int insertToBST(TreeNode *root, int value) {
TreeNode *node = root;
int smallerNum = 0;
while (node)
{
if (value < node->val)
{
node->leftNum++;
if (!node->left)
{
node->left = new TreeNode(value);
break;
}
node = node->left;
}
else if (value > node->val)
{
smallerNum += node->dupNum + node->leftNum;
if (!node->right)
{
node->right = new TreeNode(value);
break;
}
node = node->right;
}
else
{
smallerNum += node->leftNum;
node->dupNum++;
break;
}
}
return smallerNum;
}
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> res;
int n = nums.size();
if (n == 0)
return res;
TreeNode root(nums[n-1]);
res.push_back(0);
for (int i = nums.size()-2; i >= 0; --i)
{
res.insert(res.begin(), insertToBST(&root, nums[i]));
}
return res;
}
};