Domain 1EasyCORE

How Many Numbers Are Smaller Than the Current Number

The problem requires us to find out for each element in the array `nums`, how many other elements are smaller than it. The input is an array of integers, and the output should be an array where each element at index `i` represents the count of numbers in `nums` that are smaller than the corresponding element in `nums`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

1365. How Many Numbers Are Smaller Than the Current Number

Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 86.0%


Problem Breakdown

The problem requires us to find out for each element in the array nums, how many other elements are smaller than it. The input is an array of integers, and the output should be an array where each element at index i represents the count of numbers in nums that are smaller than the corresponding element in nums.

Inputs:

  • An array nums of integers.

Outputs:

  • An array where each element is the count of numbers in nums that are smaller than the corresponding element in nums.

Implicit Constraints or Edge Cases:

  • The array can contain duplicate values.
  • All elements in the array are non-negative integers (0 to 100).
  • The length of the array is between 2 and 500.

Intuition

A brute-force approach would involve, for each element in nums, iterating through the entire array again to count how many elements are smaller. This approach has a time complexity of O(n^2), which is inefficient given the constraints.

The key insight is that we can sort the array and use the sorted order to determine the number of elements smaller than any given element. By mapping each unique element in the sorted array to its index, we can quickly find out how many elements are smaller for any given element in the original array.

Approach

  1. Sort the Array: Create a sorted version of the input array nums. This will help us determine the relative order of elements.
  2. Create a Mapping: Use a dictionary to map each unique element in the sorted array to its index. The index represents how many elements are smaller than that particular value.
  3. Generate Result Array: Iterate through the original array and use the mapping to find out how many elements are smaller for each element, constructing the result array.

Complexity Analysis

  • Time Complexity: O(n log n) due to the sorting step. The dictionary operations (insertion and lookup) are O(1) on average.
  • Space Complexity: O(n) for storing the sorted array and the mapping dictionary.

Solution

def smallerNumbersThanCurrent(nums):
    # Step 1: Sort the array
    sorted_nums = sorted(nums)
    
    # Step 2: Create a mapping from element to its index in the sorted array
    rank_map = {num: idx for idx, num in enumerate(sorted_nums)}
    
    # Step 3: Generate the result array using the mapping
    result = [rank_map[num] for num in nums]
    
    return result

# Example usage:
nums1 = [8, 1, 2, 2, 3]
print(smallerNumbersThanCurrent(nums1))  # Output: [4, 0, 1, 1, 3]

nums2 = [6, 5, 4, 8]
print(smallerNumbersThanCurrent(nums2))  # Output: [2, 1, 0, 3]

nums3 = [7, 7, 7, 7]
print(smallerNumbersThanCurrent(nums3))  # Output: [0, 0, 0, 0]

Edge Cases Handled

  • Duplicates: The mapping handles duplicates correctly by assigning the same index to identical values.
  • All Elements Equal: If all elements are equal, the result will be an array of zeros, as no element is smaller than another.
  • Single Element Array: Although not explicitly mentioned in constraints, if the input were a single-element array, the function would return [0] since there are no other elements to compare against.