How Many Numbers Are Smaller Than the Current Number · Interview Problem

Back to problems

Leetcode

Easy

Arrays

Hash Maps

Sorting

How Many Numbers Are Smaller Than the Current Number

Count, for each number in an array, how many values are strictly smaller than it.

Acceptance 100%

Start Practice

Problem Statement

Problem

Given an integer array nums, return a new array answer such that answer[i] is the number of elements in nums that are strictly smaller than nums[i].

You must compute this for every position independently.

Notes

Equal values do not count as smaller.
The order of results should match the original order of nums.

Input Format

A single integer array nums.

Output Format

An integer array answer where each entry contains the count of values in nums that are smaller than the corresponding value.

Constraints

1 <= nums.length <= 500
0 <= nums[i] <= 100

Hints

The values are in a small range, so you may be able to count occurrences first.
Another option is to sort a copy of the array and determine how many elements come before each value.

Input Format

An integer array nums.

Output Format

Return an integer array answer of the same length as nums.

Constraints

1 <= nums.length <= 500
0 <= nums[i] <= 100
Output counts strictly smaller values only.

Examples

Sample cases returned by the problem API.

Example 1

Input

nums = [8,1,2,2,3]

Output

[4,0,1,1,3]

Explanation

8 has 4 numbers smaller than it: 1, 2, 2, 3
1 has 0 numbers smaller than it
2 has 1 number smaller than it: 1
2 has 1 number smaller than it: 1
3 has 3 numbers smaller than it: 1, 2, 2

Example 2

Input

nums = [6,5,4,8]

Output

[2,1,0,3]

Explanation

6 has 2 smaller numbers: 5, 4
5 has 1 smaller number: 4
4 has 0 smaller numbers
8 has 3 smaller numbers: 6, 5, 4

Show 1 more example

Example 3

Input

nums = [7,7,7,7]

Output

[0,0,0,0]

Explanation

All values are equal, so none of them has a strictly smaller value in the array.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress