Count of Smaller Numbers After Self solution and explanation
Google
Infosys
9 more videos on this problem
Count of Smaller Numbers After Self | Leetcode June Challenge | Leetcode 315 | C++ | Approach + CodeAyushi Sharma · 16:27 · 35K views
315. Count of Smaller Numbers After Self | Day 024 | Fenwick Tree | Merge SortAryan Mittal · 29:25 · 21K views
[New Solution Link Below] LeetCode 315.Count of Smaller Numbers After Self Explanation and Solutionhappygirlzt · 15:37 · 18K views
leetcode 315 Count of Smaller Numbers After SelfCodebix · 16:10 · 12K views
COUNT OF SMALLER NUMBERS AFTER SELF | LEETCODE 315 | PYTHON BINARY SEARCH SOLUTIONCracking FAANG · 18:46 · 9K views
Leetcode - Count of Smaller Numbers After Self (Python)Timothy H Chang · 8:27 · 7K views
LeetCode 315. Count of Smaller Numbers After SelfHappy Coding · 28:22 · 3K views
[Binary Indexed Tree] LeetCode 315 Count of Smaller Numbers After Selfhappygirlzt · 14:06 · 1K views
Leetcode 315 Count of Smaller Numbers After Self (Java)TheAnalyticGuy · 9:37 · 1K views
Daily Leetcode #844: Jul 23, 2022 - 315. Count of Smaller Numbers After SelfProgramming Live with Larry · 7:11 · 1K views
The problem
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
Approach overview
Problem Overview: Given an integer array nums, compute how many smaller elements appear to the right of every index. For each position i, you need the count of numbers nums[j] such that j > i and nums[j] < nums[i]. The output is an array where each value represents that count.
Approach 1: Binary Indexed Tree (Fenwick Tree) (Time: O(n log n), Space: O(n))
This approach processes the array from right to left and uses a Binary Indexed Tree to maintain frequencies of numbers seen so far. Because values may be large or negative, the first step is coordinate compression: map each number to a rank in a sorted order. For every element, query the Fenwick Tree for the prefix sum of ranks smaller than the current value. That prefix sum equals the number of smaller elements already processed (which are to the right in the original array). After the query, update the tree with the current element's rank. Both query and update operations run in O(log n), giving a total complexity of O(n log n).
Approach 2: Divide and Conquer with Binary Search Tree (Time: O(n log n) average, Space: O(n))
This approach builds a Binary Search Tree while scanning the array from right to left. Each node stores the value, the number of nodes in its left subtree, and a duplicate count. When inserting a new number, traverse the tree and accumulate counts: moving right means all nodes in the current node's left subtree plus duplicates are smaller than the inserted value. Moving left increments the left subtree count because a new smaller element is added. The final accumulated value becomes the answer for that index. On average the insertion cost is O(log n), producing O(n log n) overall time, though the worst case can degrade to O(n²) if the tree becomes skewed.
Both solutions rely on efficient counting structures rather than comparing each pair of elements. Problems like this commonly appear in advanced array counting tasks alongside techniques such as merge sort inversion counting and segment trees.
Recommended for interviews: The Fenwick Tree solution is usually the strongest answer. It guarantees O(n log n) time, avoids worst‑case degradation, and demonstrates knowledge of prefix-sum data structures. Explaining the BST method still shows strong reasoning about ordered structures and incremental counting, but interviewers generally prefer Fenwick Tree or merge‑sort based counting because the complexity remains predictable.
Approach 1: Approach 1: Binary Indexed Tree (Fenwick Tree)
The Binary Indexed Tree (BIT) allows us to efficiently update elements and calculate cumulative frequencies in an iterative manner. In this approach, we traverse the input array from right to left, update the BIT with the index of the current number, and use the BIT to find the count of numbers which are smaller.
class FenwickTree:
def __init__(self, size):
self.tree = [0] * (size + 1)
def update(self, index, value):
while index < len(self.tree):
self.tree[index] += value
index += index & -index
def query(self, index):
sum = 0
while index > 0:
sum += self.tree[index]
index -= index & -index
return sum
def countSmaller(nums):
offset = 10000
size = 20001
bit = FenwickTree(size)
result = [0] * len(nums)
for i in range(len(nums)-1, -1, -1):
result[i] = bit.query(nums[i] + offset)
bit.update(nums[i] + offset + 1, 1)
return result
nums = [5, 2, 6, 1]
print(countSmaller(nums))import java.util.*;
class Solution {
class FenwickTree {
private int[] tree;
public FenwickTree(int size) {
tree = new int[size + 1];
}
public void update(int index, int value) {
while (index < tree.length) {
tree[index] += value;
index += index & -index;
}
}
public int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
}
public List<Integer> countSmaller(int[] nums) {
int offset = 10000;
int size = 20001;
FenwickTree bit = new FenwickTree(size);
Integer[] result = new Integer[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
result[i] = bit.query(nums[i] + offset);
bit.update(nums[i] + offset + 1, 1);
}
return Arrays.asList(result);
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 2, 6, 1};
List<Integer> result = solution.countSmaller(nums);
System.out.println(result);
}
}#include <vector>
#include <iostream>
using namespace std;
class BIT {
vector<int> tree;
public:
BIT(int size) : tree(size + 1, 0) {}
void update(int index, int value) {
while (index < tree.size()) {
tree[index] += value;
index += index & -index;
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
};
vector<int> countSmaller(vector<int>& nums) {
int offset = 10000; // Offset negative indices
int size = 20001; // Total possible discrete values
BIT bit(size);
vector<int> result(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
result[i] = bit.query(nums[i] + offset);
bit.update(nums[i] + offset + 1, 1);
}
return result;
}
int main() {
vector<int> nums = {5, 2, 6, 1};
vector<int> result = countSmaller(nums);
for (int num : result) {
cout << num << " ";
}
return 0;
}class FenwickTree {
constructor(size) {
this.tree = new Array(size + 1).fill(0);
}
update(index, value) {
while (index < this.tree.length) {
this.tree[index] += value;
index += index & -index;
}
}
query(index) {
let sum = 0;
while (index > 0) {
sum += this.tree[index];
index -= index & -index;
}
return sum;
}
}
const countSmaller = function (nums) {
const offset = 10000;
const size = 20001;
const bit = new FenwickTree(size);
const result = new Array(nums.length).fill(0);
for (let i = nums.length - 1; i >= 0; i--) {
result[i] = bit.query(nums[i] + offset);
bit.update(nums[i] + offset + 1, 1);
}
return result;
};
const nums = [5, 2, 6, 1];
console.log(countSmaller(nums));#include <stdio.h>
#include <stdlib.h>
#define MAX 100000
int bit[MAX + 1];
int* getCounts(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* result = (int*) calloc(numsSize, sizeof(int));
int minVal = -10000, maxVal = 10000;
for (int i = numsSize - 1; i >= 0; i--) {
int index = nums[i] - minVal + 1;
int sum = 0, j = index - 1;
while (j > 0) {
sum += bit[j];
j -= (j & -j);
}
result[i] = sum;
j = index;
while (j <= MAX) {
bit[j]++;
j += (j & -j);
}
}
return result;
}
int main() {
int nums[] = {5, 2, 6, 1};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* counts = getCounts(nums, numsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", counts[i]);
}
free(counts);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public class FenwickTree {
private int[] tree;
public FenwickTree(int size) {
tree = new int[size + 1];
}
public void Update(int index, int value) {
while (index < tree.Length) {
tree[index] += value;
index += index & -index;
}
}
public int Query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & -index;
}
return sum;
}
}
public IList<int> CountSmaller(int[] nums) {
int offset = 10000;
int size = 20001;
FenwickTree bit = new FenwickTree(size);
int[] result = new int[nums.Length];
for (int i = nums.Length - 1; i >= 0; i--) {
result[i] = bit.Query(nums[i] + offset);
bit.Update(nums[i] + offset + 1, 1);
}
return result;
}
static void Main() {
Solution solution = new Solution();
int[] nums = {5, 2, 6, 1};
IList<int> result = solution.CountSmaller(nums);
Console.WriteLine(string.Join(" ", result));
}
}This Python script implements the Binary Indexed Tree through a FenwickTree class. By applying an offset to the input values, it ensures all indices used with the BIT are positive. By iterating from right to left over the input list, it queries the BIT for the number of less-than elements and updates the current element into the BIT.
Time Complexity: O(n log n), where n is the size of nums. The complexity stems from the logarithmic time BIT operations.
Space Complexity: O(n) due to the additional storage of the BIT and result list.
Approach 2: Approach 2: Divide and Conquer with Binary Search Tree
This approach takes advantage of the divide and conquer strategy combined with a binary search tree (BST). As we process each number from right to left, we insert them into the BST, which allows us to compute the count of elements smaller than the current number efficiently.
class TreeNode:
def __init__(self, val):
self.val = val
self.left_count = 0
self.dup = 1
self.left = self.right = None
def insert(node, val, pre_sum):
if not node:
return TreeNode(val)
elif node.val == val:
node.dup += 1
pre_sum[0] += node.left_count
elif node.val > val:
node.left_count += 1
node.left = insert(node.left, val, pre_sum)
else:
pre_sum[0] += node.dup + node.left_count
node.right = insert(node.right, val, pre_sum)
return node
def count_smaller(nums):
result = []
root = None
for num in reversed(nums):
pre_sum = [0]
root = insert(root, num, pre_sum)
result.append(pre_sum[0])
return result[::-1]
nums = [5, 2, 6, 1]
print(count_smaller(nums))import java.util.*;
class Solution {
class TreeNode {
int val, sum, dup;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.sum = 0;
this.dup = 1;
}
}
public List<Integer> countSmaller(int[] nums) {
Integer[] result = new Integer[nums.length];
TreeNode root = null;
for (int i = nums.length - 1; i >= 0; i--) {
int[] preSum = {0};
root = insert(root, nums[i], preSum);
result[i] = preSum[0];
}
return Arrays.asList(result);
}
private TreeNode insert(TreeNode node, int val, int[] preSum) {
if (node == null) {
return new TreeNode(val);
} else if (node.val == val) {
node.dup++;
preSum[0] += node.sum;
} else if (node.val > val) {
node.sum++;
node.left = insert(node.left, val, preSum);
} else {
preSum[0] += node.dup + node.sum;
node.right = insert(node.right, val, preSum);
}
return node;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {5, 2, 6, 1};
System.out.println(solution.countSmaller(nums));
}
}#include <vector>
#include <iostream>
class Solution {
private:
struct TreeNode {
int val, leftCount, count;
TreeNode* left;
TreeNode* right;
TreeNode(int v) : val(v), leftCount(0), count(1), left(NULL), right(NULL) {}
};
TreeNode* insert(TreeNode* root, int val, int* preSum) {
if (!root) {
root = new TreeNode(val);
} else if (val == root->val) {
root->count++;
*preSum += root->leftCount;
} else if (val < root->val) {
root->leftCount++;
root->left = insert(root->left, val, preSum);
} else {
*preSum += root->count + root->leftCount;
root->right = insert(root->right, val, preSum);
}
return root;
}
public:
std::vector<int> countSmaller(std::vector<int>& nums) {
int n = nums.size();
std::vector<int> result(n, 0);
TreeNode* root = NULL;
for (int i = n - 1; i >= 0; --i) {
int preSum = 0;
root = insert(root, nums[i], &preSum);
result[i] = preSum;
}
return result;
}
};
int main() {
Solution solution;
std::vector<int> nums = {5, 2, 6, 1};
std::vector<int> result = solution.countSmaller(nums);
for (int count : result) {
std::cout << count << " ";
}
return 0;
}class TreeNode {
constructor(val) {
this.val = val;
this.leftCount = 0;
this.dup = 1;
this.left = this.right = null;
}
}
function insert(node, val, preSum) {
if (!node) {
return new TreeNode(val);
} else if (node.val === val) {
node.dup++;
preSum[0] += node.leftCount;
} else if (node.val > val) {
node.leftCount++;
node.left = insert(node.left, val, preSum);
} else {
preSum[0] += node.dup + node.leftCount;
node.right = insert(node.right, val, preSum);
}
return node;
}
function countSmaller(nums) {
const result = new Array(nums.length).fill(0);
let root = null;
for (let i = nums.length - 1; i >= 0; i--) {
const preSum = [0];
root = insert(root, nums[i], preSum);
result[i] = preSum[0];
}
return result;
}
const nums = [5, 2, 6, 1];
console.log(countSmaller(nums));#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val, sum, dup;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* insert(TreeNode* root, int val, int* preSum) {
if (!root) {
root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->sum = 0;
root->dup = 1;
root->left = NULL;
root->right = NULL;
} else if (root->val == val) {
root->dup++;
*preSum += root->sum;
} else if (root->val > val) {
root->sum++;
root->left = insert(root->left, val, preSum);
} else {
*preSum += root->dup + root->sum;
root->right = insert(root->right, val, preSum);
}
return root;
}
int* countSmaller(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* result = (int*)malloc(numsSize * sizeof(int));
if (numsSize == 0) return result;
TreeNode* root = NULL;
for (int i = numsSize - 1; i >= 0; i--) {
int preSum = 0;
root = insert(root, nums[i], &preSum);
result[i] = preSum;
}
return result;
}
int main() {
int nums[] = {5, 2, 6, 1};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* counts = countSmaller(nums, numsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", counts[i]);
}
free(counts);
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public class TreeNode {
public int val, leftCount, dup;
public TreeNode left, right;
public TreeNode(int v) {
val = v;
leftCount = 0;
dup = 1;
}
}
public IList<int> CountSmaller(int[] nums) {
List<int> result = new List<int>(new int[nums.Length]);
TreeNode root = null;
for (int i = nums.Length - 1; i >= 0; i--) {
int[] preSum = {0};
root = Insert(root, nums[i], preSum);
result[i] = preSum[0];
}
return result;
}
private TreeNode Insert(TreeNode node, int val, int[] preSum) {
if (node == null) {
return new TreeNode(val);
} else if (node.val == val) {
node.dup++;
preSum[0] += node.leftCount;
} else if (node.val > val) {
node.leftCount++;
node.left = Insert(node.left, val, preSum);
} else {
preSum[0] += node.dup + node.leftCount;
node.right = Insert(node.right, val, preSum);
}
return node;
}
static void Main() {
Solution solution = new Solution();
int[] nums = {5, 2, 6, 1};
IList<int> result = solution.CountSmaller(nums);
Console.WriteLine(string.Join(" ", result));
}
}Using a BST, this Python solution integrates a TreeNode class to capture the node value and left subtree count. Recursive insert operations enable the computation of smaller elements using the pre_sum array, with insertion following the tree structure rules to balance the BST throughout traversal.
Time Complexity: O(n log n), assuming the BST remains balanced effectively.
Space Complexity: O(n) due to the nodes in the BST and final list of results.
Approach 3: Default Approach
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}
func countSmaller(nums []int) []int {
s := make(map[int]bool)
for _, v := range nums {
s[v] = true
}
var alls []int
for v := range s {
alls = append(alls, v)
}
sort.Ints(alls)
m := make(map[int]int)
for i, v := range alls {
m[v] = i + 1
}
ans := make([]int, len(nums))
tree := newBinaryIndexedTree(len(alls))
for i := len(nums) - 1; i >= 0; i-- {
x := m[nums[i]]
tree.update(x, 1)
ans[i] = tree.query(x - 1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Binary Indexed Tree (Fenwick Tree) | Time Complexity: O(n log n), where n is the size of |
| Approach 2: Divide and Conquer with Binary Search Tree | Time Complexity: O(n log n), assuming the BST remains balanced effectively. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Indexed Tree (Fenwick Tree) | O(n log n) | O(n) | Best general solution with guaranteed performance and efficient prefix queries. |
| Binary Search Tree Counting | O(n log n) average, O(n²) worst | O(n) | Useful when demonstrating ordered set or BST augmentation techniques. |
Frequently asked questions
Is Count of Smaller Numbers After Self easy or hard?
LeetCode classifies this problem as Hard because it requires advanced counting techniques such as Fenwick Trees, Segment Trees, or merge sort based divide-and-conquer. A brute force approach is easy to understand but runs in O(n²) time and fails large inputs.
Count of Smaller Numbers After Self Python or Java solution?
Typical implementations in Python or Java use a Fenwick Tree with coordinate compression. The array is processed from right to left, performing prefix sum queries and updates in O(log n). The full solution runs in O(n log n) time with O(n) extra space.
How to solve Count of Smaller Numbers After Self in O(n log n)?
Traverse the array from right to left while maintaining a Fenwick Tree or Segment Tree of frequencies. Query how many numbers smaller than the current value have already appeared, then insert the current value into the structure. Each query and update costs O(log n).
What is the best approach for Count of Smaller Numbers After Self?
The most reliable approach uses a Binary Indexed Tree (Fenwick Tree). Process the array from right to left, query the tree for how many smaller ranks already exist, then update the tree with the current number. This guarantees O(n log n) time and O(n) space.
Is Count of Smaller Numbers After Self asked at Google/Amazon/Meta?
Count of Smaller Numbers After Self is a well-known hard interview problem and variations have appeared in interviews at companies like Google, Amazon, Meta, and other large tech firms. It tests knowledge of Fenwick Trees, merge sort counting, and ordered data structures.
What data structure is used in Count of Smaller Numbers After Self?
Common data structures include Binary Indexed Trees (Fenwick Trees), Segment Trees, augmented Binary Search Trees, and merge sort based counting. Each structure allows efficient counting of elements smaller than a given value in logarithmic time.
What is the time complexity of Count of Smaller Numbers After Self?
Optimal solutions run in O(n log n) time. Fenwick Tree, Segment Tree, and merge sort based counting all achieve this complexity by avoiding pairwise comparisons and using logarithmic updates or merges.