How Many Numbers Are Smaller Than the Current Number solution and explanation
Google
TCS
9 more videos on this problem
Numbers Smaller than current Number (LeetCode 1365) | Full solution with examples | Study AlgorithmsNikhil Lohia · 16:12 · 25K views
LeetCode 1365 | How Many Numbers are Smaller than Current Number | Algorithm Explained (Java)Xavier Elon · 9:41 · 13K views
How Many Numbers Are Smaller Than the Current Number | Leetcode - 1365Algorithms Made Easy · 6:16 · 5K views
1365. How Many Numbers Are Smaller Than the Current Number || leetcode || easy prob || c++ solutioncode Explainer · 4:51 · 4K views
LeetCode - How Many Numbers Are Smaller Than the Current Number - PythonKnowledge Mavens · 8:41 · 3K views
Leetcode Solution - 1365 How Many Numbers Are Smaller Than the Current NumberJohn Leonardo · 6:01 · 1K views
LeetCode 1365. How Many Numbers Are Smaller Than the Current Number | pythonEric Lee · 8:52 · 1K views
LeetCode #1365. How Many Numbers Are Smaller Than the Current Number | JavascriptDarwin Tech · 5:19 · 1K views
How Many Numbers Are Smaller Than the Current Number - Leetcode 1365 (Python)nexTRIE · 4:40 · 983 views
1365 how many number are smaller than current number leetcode problem in c++| leetcode for beginnersCoding enthusiast · 5:52 · 824 views
The problem
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].
Return the answer in an array.
Example 1:
Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:
Input: nums = [6,5,4,8] Output: [2,1,0,3]
Example 3:
Input: nums = [7,7,7,7] Output: [0,0,0,0]
Constraints:
2 <= nums.length <= 5000 <= nums[i] <= 100
Approach overview
Problem Overview: You receive an integer array nums. For each element, compute how many numbers in the array are strictly smaller than it. The output is another array where result[i] equals the count of values less than nums[i].
Approach 1: Brute Force Comparison (O(n^2) time, O(1) space)
The direct solution compares every element with every other element. For each index i, iterate through the entire array again and count how many values are smaller than nums[i]. This uses two nested loops and increments a counter whenever nums[j] < nums[i]. The logic is simple and requires no extra data structures beyond the output array. This approach is useful for understanding the problem constraints but becomes inefficient when n grows because the comparisons scale quadratically.
Approach 2: Sorting with Rank Mapping (O(n log n) time, O(n) space)
A faster method sorts the numbers and records the first index where each value appears. After sorting, the index of a number represents how many values are smaller than it. Traverse the sorted array and store the first occurrence of each number in a hash map so duplicates share the same count. Then iterate through the original array and replace each value with its mapped index. Sorting reduces the number of comparisons and the hash lookup provides constant‑time access for each element.
This approach combines sorting with a hash table to map values to their rank. The input array itself is still processed sequentially, which aligns naturally with typical array operations.
Recommended for interviews: Interviewers usually expect the sorting approach. The brute force version proves you understand the definition of the problem, but the sorted ranking technique demonstrates that you can reduce repeated comparisons using preprocessing. Mentioning how duplicates are handled with a hash map is often the key insight they want to hear.
Approach 1: Brute Force Approach
In this approach, we simply iterate over the array for each element, comparing it with every other element to count how many numbers are smaller. This is a straightforward nested loop approach where the outer loop picks the current number and the inner loop counts numbers smaller than it.
def smallerNumbersThanCurrent(nums):
result = []
for i in range(len(nums)):
count = 0
for j in range(len(nums)):
if nums[j] < nums[i]:
count += 1
result.append(count)
return result
nums = [8, 1, 2, 2, 3]
print(smallerNumbersThanCurrent(nums))import java.util.*;
public class Solution {
public static int[] smallerNumbersThanCurrent(int[] nums) {
int[] result = new int[nums.length];
for(int i = 0; i < nums.length; i++) {
int count = 0;
for(int j = 0; j < nums.length; j++) {
if(nums[j] < nums[i]) {
count++;
}
}
result[i] = count;
}
return result;
}
public static void main(String[] args) {
int[] nums = {8, 1, 2, 2, 3};
int[] result = smallerNumbersThanCurrent(nums);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
std::vector<int> result(nums.size(), 0);
for(int i = 0; i < nums.size(); i++) {
for(int j = 0; j < nums.size(); j++) {
if(nums[j] < nums[i]) {
result[i]++;
}
}
}
return result;
}
int main() {
std::vector<int> nums = {8, 1, 2, 2, 3};
std::vector<int> result = smallerNumbersThanCurrent(nums);
for(int num : result) {
std::cout << num << " ";
}
return 0;
}function smallerNumbersThanCurrent(nums) {
let result = [];
for(let i = 0; i < nums.length; i++) {
let count = 0;
for(let j = 0; j < nums.length; j++) {
if(nums[j] < nums[i]) {
count++;
}
}
result.push(count);
}
return result;
}
let nums = [8, 1, 2, 2, 3];
console.log(smallerNumbersThanCurrent(nums));#include <stdio.h>
void smallerNumbersThanCurrent(int* nums, int numsSize, int* result) {
for(int i = 0; i < numsSize; i++) {
int count = 0;
for(int j = 0; j < numsSize; j++) {
if(nums[j] < nums[i]) {
count++;
}
}
result[i] = count;
}
}
int main() {
int nums[] = {8, 1, 2, 2, 3};
int numsSize = sizeof(nums)/sizeof(nums[0]);
int result[numsSize];
smallerNumbersThanCurrent(nums, numsSize, result);
for(int i = 0; i < numsSize; i++) {
printf("%d ", result[i]);
}
return 0;
}using System;
public class Solution {
public static int[] SmallerNumbersThanCurrent(int[] nums) {
int[] result = new int[nums.Length];
for(int i = 0; i < nums.Length; i++) {
int count = 0;
for(int j = 0; j < nums.Length; j++) {
if(nums[j] < nums[i]) {
count++;
}
}
result[i] = count;
}
return result;
}
public static void Main() {
int[] nums = {8, 1, 2, 2, 3};
Console.WriteLine(string.Join(", ", SmallerNumbersThanCurrent(nums)));
}
}This Python function iterates through each element in nums with an outer loop, and counts how many numbers are smaller using an inner loop, appending the result to the result list.
Time Complexity: O(n^2). Space Complexity: O(n) due to the list used to hold the count of smaller numbers.
Approach 2: Optimal Sorting Approach
This approach uses sorting to achieve a more efficient solution. We sort a copy of the array while keeping track of the indices and then assign the number of lesser elements directly based on sorted positions.
def smallerNumbersThanCurrent(nums):
sorted_nums = sorted(nums)
result = []
for num in nums:
result.append(sorted_nums.index(num))
return result
nums = [8, 1, 2, 2, 3]
print(smallerNumbersThanCurrent(nums))import java.util.*;
public class Solution {
public static int[] smallerNumbersThanCurrent(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = Arrays.binarySearch(sorted, nums[i]);
}
return result;
}
public static void main(String[] args) {
int[] nums = {8, 1, 2, 2, 3};
int[] result = smallerNumbersThanCurrent(nums);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
std::vector<int> sorted = nums;
std::sort(sorted.begin(), sorted.end());
std::vector<int> result(nums.size());
for (int i = 0; i < nums.size(); ++i) {
result[i] = std::lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin();
}
return result;
}
int main() {
std::vector<int> nums = {8, 1, 2, 2, 3};
std::vector<int> result = smallerNumbersThanCurrent(nums);
for (int num : result) {
std::cout << num << " ";
}
return 0;
}function smallerNumbersThanCurrent(nums) {
let sorted = [...nums].sort((a, b) => a - b);
return nums.map(num => sorted.indexOf(num));
}
let nums = [8, 1, 2, 2, 3];
console.log(smallerNumbersThanCurrent(nums));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {
*returnSize = numsSize;
int* sorted = (int*)malloc(numsSize * sizeof(int));
int* result = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; ++i) sorted[i] = nums[i];
qsort(sorted, numsSize, sizeof(int), cmp);
for (int i = 0; i < numsSize; ++i) {
int count = 0;
for (int j = 0; j < numsSize; ++j) {
if (sorted[j] < nums[i]) count++;
else break;
}
result[i] = count;
}
free(sorted);
return result;
}
int main() {
int nums[] = {8, 1, 2, 2, 3};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int returnSize;
int* result = smallerNumbersThanCurrent(nums, numsSize, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
free(result);
return 0;
}using System;
using System.Linq;
public class Solution {
public static int[] SmallerNumbersThanCurrent(int[] nums) {
int[] sorted = (int[])nums.Clone();
Array.Sort(sorted);
int[] result = new int[nums.Length];
for(int i = 0; i < nums.Length; i++) {
result[i] = Array.IndexOf(sorted, nums[i]);
}
return result;
}
public static void Main() {
int[] nums = {8, 1, 2, 2, 3};
Console.WriteLine(string.Join(", ", SmallerNumbersThanCurrent(nums)));
}
}This Python solution sorts the input list and uses the index() method, which effectively does the same job as binary searching in the sorted list to determine the number of smaller elements.
Time Complexity: O(n^2) due to the use of index in sorted list for each element. Space Complexity: O(n).
Approach 3: Sorting + Binary Search
We can make a copy of the array nums, denoted as arr, and then sort arr in ascending order.
Next, for each element x in nums, we can use binary search to find the index j of the first element that is greater than or equal to x. Then j is the number of elements that are smaller than x. We can store j in the answer array.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the length of the array nums.
function smallerNumbersThanCurrent(nums: number[]): number[] {
const search = (nums: number[], x: number) => {
let l = 0,
r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const arr = nums.slice().sort((a, b) => a - b);
for (let i = 0; i < nums.length; ++i) {
nums[i] = search(arr, nums[i]);
}
return nums;
}func smallerNumbersThanCurrent(nums []int) (ans []int) {
arr := make([]int, len(nums))
copy(arr, nums)
sort.Ints(arr)
for i, x := range nums {
nums[i] = sort.SearchInts(arr, x)
}
return nums
}Approach 4: Counting Sort + Prefix Sum
We notice that the range of elements in the array nums is [0, 100]. Therefore, we can use the counting sort method to first count the number of each element in the array nums. Then we calculate the prefix sum of the counting array. Finally, we traverse the array nums. For each element x, we directly add the value of the element at index x in the counting array to the answer array.
The time complexity is O(n + M), and the space complexity is O(M). Where n and M are the length and the maximum value of the array nums, respectively.
function smallerNumbersThanCurrent(nums: number[]): number[] {
const cnt: number[] = new Array(102).fill(0);
for (const x of nums) {
++cnt[x + 1];
}
for (let i = 1; i < cnt.length; ++i) {
cnt[i] += cnt[i - 1];
}
const n = nums.length;
const ans: number[] = new Array(n);
for (let i = 0; i < n; ++i) {
ans[i] = cnt[nums[i]];
}
return ans;
}func smallerNumbersThanCurrent(nums []int) (ans []int) {
cnt := [102]int{}
for _, x := range nums {
cnt[x+1]++
}
for i := 1; i < len(cnt); i++ {
cnt[i] += cnt[i-1]
}
for _, x := range nums {
ans = append(ans, cnt[x])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2). Space Complexity: O(n) due to the list used to hold the count of smaller numbers. |
| Optimal Sorting Approach | Time Complexity: O(n^2) due to the use of index in sorted list for each element. Space Complexity: O(n). |
| Sorting + Binary Search | – |
| Counting Sort + Prefix Sum | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n^2) | O(1) | Small arrays or when demonstrating the basic logic during interviews |
| Sorting with Rank Mapping | O(n log n) | O(n) | General case solution that avoids repeated comparisons and handles duplicates efficiently |
Frequently asked questions
Is How Many Numbers Are Smaller Than the Current Number easy or hard?
LeetCode classifies this problem as Easy. The logic is straightforward with brute force, and the optimized version introduces standard techniques like sorting or counting arrays, which makes it a common early interview practice question.
How Many Numbers Are Smaller Than the Current Number Python/Java solution
In Python or Java, the common pattern is: copy and sort the array, store the first index of each number in a hash map, then iterate through the original array and replace each element with the stored rank. This produces the result in O(n log n) time.
How to solve How Many Numbers Are Smaller Than the Current Number in O(n)?
A linear solution is possible using counting because the values in the problem are limited (0–100 in the original constraints). Create a frequency array, build prefix sums to know how many numbers are smaller than each value, and then map results back to the original array. This runs in O(n + k) time where k is the value range.
What is the best approach for How Many Numbers Are Smaller Than the Current Number?
The commonly expected solution sorts the array and maps each value to its first index in the sorted order. That index represents how many numbers are smaller than it. This approach runs in O(n log n) time due to sorting and uses O(n) extra space for the hash map and result array.
Is How Many Numbers Are Smaller Than the Current Number asked at Google/Amazon/Meta?
This problem appears frequently in coding practice sets and has been reported in interview preparation for companies like Amazon and other large tech firms. It mainly tests understanding of arrays, sorting, and basic counting techniques rather than complex algorithms.
What data structure is used in How Many Numbers Are Smaller Than the Current Number?
Typical implementations use arrays for traversal and a hash table (or dictionary) to map each number to its rank after sorting. Some optimized solutions also use a counting array to compute prefix sums when the value range is small.
What is the time complexity of How Many Numbers Are Smaller Than the Current Number?
The brute force solution runs in O(n^2) time because every element is compared with every other element. The optimized sorting approach improves this to O(n log n) time with O(n) extra space for storing ranks.