LeetCode (1365)How Many Numbers Are Smaller Than the Current Number
Counting Sort / Prefix Sums
Asked at 6 companies
4 recent
- Bloomberg
- Microsoft
- Meta
- Amazon
- tcs
Community-reported · source · updated 2026-10-08. ● asked in the last 6 months.
Go step by step: try it yourself before the video and the visual. Progress saves on this device.
0 / 110 pointsSolved (Easy) 0/20Reviews 0/50Mastered 0/25Practice steps 0/15
Step 1
Know these before you start
Practise each one here, or tick what you already know
Concept videoWatch the concept video if the pattern is new to you.
Step 2
Try it on paper
5–10 minutes, no code yet
ProblemProblem statementGiven the array nums, for each nums[i] find out how many numbers in the array are smaller than it. Return the answer in an array.ReadHide
Problem Statement
Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. Return the answer in an array.
Added 2026-11-05 from Srujan's LeetCode Recent AC list (photo) — not previously in the repo.
Input / Output
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
Input: nums = [7,7,7,7]
Output: [0,0,0,0]
Code it on LeetCode
There's no editor for this one here yet, so solve it on LeetCode, with its own tests. Then tick My code passed below, and it joins your reviews. With your LeetCode account linked, that happens on its own.
Solve on LeetCode Step 6
Get it accepted
All test cases pass
Step 7
Review it so it sticks
Re-solve from memory after
The step that matters most: without reviews most of a solved problem fades within weeks. Three short re-solves, each just as you start to forget, are what make it yours.
Your notes
Three lines in your own words. They come back with this problem's reviews, so you can check yourself after recalling the solution.
Solve it yourself before you look
Reading the solution first feels like progress, but it makes the next similar problem — and the interview version — much harder, because you skipped the part where you figure it out. Give it an honest 20–30 minutes. Stuck? Re-read the pattern, watch the concept video, or try the brute force first.
Hidden: approach · solution code
Approach
Pattern Recognition
Counting Sort / Prefix Sums — the values are bounded (0 to 100), so instead of comparing every pair, count how many times each value appears, then turn those counts into "how many are smaller than x" with a running total. One pass to count, one pass to answer.
Approach
Brute Force — Compare Every Pair, O(n²)
for i in range(len(nums)):
answer[i] = count of j where nums[j] < nums[i]
Optimized — Count + Prefix Sums, O(n)
count[v] = how many times value v appears
smaller[v] = count[0] + count[1] + ... + count[v-1] # running total
answer[i] = smaller[nums[i]]
Complexity
| Approach | Time | Space | Notes |
|---|---|---|---|
| Compare pairs | O(n²) | O(1) extra | Simple, re-compares everything |
| Count + prefix | O(n) | O(101) | Bounded values make it free |
Solution code
from typing import List
class SolutionBruteForce:
"""O(n^2) time | O(1) extra space — compare every pair."""
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
answer = []
for i in range(len(nums)):
count = 0
for j in range(len(nums)):
if nums[j] < nums[i]:
count += 1
answer.append(count)
return answer
class Solution:
"""O(n) time | O(101) space — count values, then prefix sums."""
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
count = [0] * 101
for v in nums:
count[v] += 1
smaller = [0] * 101
running = 0
for v in range(101):
smaller[v] = running
running += count[v]
return [smaller[v] for v in nums]Other ways to solve it
- Community solutions on LeetCode ↗ for many more versions, in many languages. Read them after you've solved it.
Revising this one?
- →Solve it from memory before peeking
- →Say the pattern out loud, not just the code
- →Explain it like you would to a friend
- →Try it again in a different language