LeetCode 1365 - How Many Numbers Are Smaller Than the Current Number

The problem asks us to determine, for each element in an array, how many elements in the same array are strictly smaller than it. In other words, for an element nums[i], we count all elements nums[j] such that nums[j] < nums[i] and j != i.

leetcodeeasyarrayhash-tablesortingcounting-sort

LeetCode Problem 1365

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Counting Sort

Solution

Problem Understanding

The problem asks us to determine, for each element in an array, how many elements in the same array are strictly smaller than it. In other words, for an element nums[i], we count all elements nums[j] such that nums[j] < nums[i] and j != i. The input is a list of integers nums with length between 2 and 500, and each element is guaranteed to be between 0 and 100 inclusive. The output is an array of the same length, where each position contains the count of smaller numbers corresponding to that index.

The constraints give us key information about potential optimizations. Since the numbers are bounded (0 to 100) and the array length is relatively small, solutions that leverage frequency counting or sorting can be very efficient. Important edge cases include arrays with duplicate values, arrays where all elements are the same, and arrays with ascending or descending order. Handling duplicates correctly is crucial because elements equal to the current number should not be counted.

Approaches

Brute Force

The naive approach is to use nested loops. For each element nums[i], iterate over the array again to count how many numbers are smaller than nums[i]. This guarantees correct results because it explicitly compares every pair, but it is inefficient. With a maximum array length of 500, this results in O(n^2) comparisons, which is acceptable for small arrays but could be slow in practice.

Optimal Approach

The key observation is that the numbers are limited to the range 0-100. This allows us to use a counting sort-like approach. First, we create a frequency array count of size 101 to record how many times each number appears. Then, by computing the prefix sum over this frequency array, we can determine, for any number x, how many numbers are strictly smaller than x. This method avoids nested loops over the input array entirely and reduces the time complexity to O(n + k), where k is 101, the fixed range of numbers.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compare each element with every other element
Optimal O(n + k) O(k) Use frequency counting and prefix sums (k = 101)

Algorithm Walkthrough

  1. Initialize a frequency array count of size 101 with all zeros. This will store how many times each number occurs in nums.
  2. Iterate over nums, incrementing count[num] for each element num. After this step, count[i] represents the frequency of i in nums.
  3. Convert count into a prefix sum array. Iterate from 1 to 100 and update count[i] to count[i] + count[i - 1]. After this, count[i] tells us how many numbers in nums are less than or equal to i.
  4. Iterate over nums again to build the result array. For each num, if num is 0, there are no smaller numbers, so append 0. Otherwise, append count[num - 1], which gives the count of numbers strictly smaller than num.
  5. Return the result array.

The algorithm works because the prefix sum captures the cumulative number of elements up to a certain value. By subtracting appropriately, we get exactly the count of elements strictly smaller than each number.

Python Solution

from typing import List

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        count = [0] * 101
        
        # Count the frequency of each number
        for num in nums:
            count[num] += 1
        
        # Compute prefix sums
        for i in range(1, 101):
            count[i] += count[i - 1]
        
        result = []
        for num in nums:
            if num == 0:
                result.append(0)
            else:
                result.append(count[num - 1])
        
        return result

The Python solution first constructs a frequency array to track how often each number appears. Next, it computes a cumulative sum to convert frequencies into counts of numbers less than or equal to each index. Finally, it constructs the result by looking up count[num - 1] for each number, which directly yields the number of smaller elements.

Go Solution

func smallerNumbersThanCurrent(nums []int) []int {
    count := make([]int, 101)
    
    // Count the frequency of each number
    for _, num := range nums {
        count[num]++
    }
    
    // Compute prefix sums
    for i := 1; i <= 100; i++ {
        count[i] += count[i - 1]
    }
    
    result := make([]int, len(nums))
    for i, num := range nums {
        if num == 0 {
            result[i] = 0
        } else {
            result[i] = count[num - 1]
        }
    }
    
    return result
}

The Go solution mirrors the Python logic, with make([]int, 101) creating the frequency array. The prefix sums and result array construction follow the same approach. Handling num == 0 ensures we avoid indexing -1.

Worked Examples

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

Step count array (partial) Explanation
Initial count [0,0,0,0,0,0,...] All zeros
Count frequencies [0,1,2,1,0,0,...,1] 1 appears once, 2 appears twice, 3 once, 8 once
Prefix sums [0,1,3,4,4,4,...,5] count[i] = numbers <= i
Build result [4,0,1,1,3] For 8 → count[7]=4, for 1 → count[0]=0, for 2 → count[1]=1, etc.

This shows how the prefix sum allows O(1) lookup for the number of smaller elements.

Complexity Analysis

Measure Complexity Explanation
Time O(n + k) Count frequencies in O(n), prefix sum in O(k) where k=101, final iteration O(n)
Space O(k) Frequency array of size 101, result array of size n

Since k=101 is constant, the algorithm is effectively linear in n.

Test Cases

# test cases
sol = Solution()
assert sol.smallerNumbersThanCurrent([8,1,2,2,3]) == [4,0,1,1,3]  # example 1
assert sol.smallerNumbersThanCurrent([6,5,4,8]) == [2,1,0,3]      # example 2
assert sol.smallerNumbersThanCurrent([7,7,7,7]) == [0,0,0,0]      # example 3
assert sol.smallerNumbersThanCurrent([0,100]) == [0,1]            # min and max boundary
assert sol.smallerNumbersThanCurrent([5]) == [0]                  # single element (edge not in constraints but safe)
assert sol.smallerNumbersThanCurrent([1,2,3,4,5]) == [0,1,2,3,4]  # ascending order
assert sol.smallerNumbersThanCurrent([5,4,3,2,1]) == [4,3,2,1,0]  # descending order
assert sol.smallerNumbersThanCurrent([2,2,2,3,3]) == [0,0,0,3,3]  # duplicates
Test Why
[8,1,2,2,3] Standard example with duplicates
[6,5,4,8] Simple distinct numbers
[7,7,7,7] All equal numbers
[0,100] Min and max numbers
[1] Single element edge case
[1,2,3,4,5] Ascending order
[5,4,3,2,1] Descending order
[2,2,2,3,3] Handling duplicates properly

Edge Cases

One edge case is when all numbers are identical. The algorithm correctly returns zero for all positions because no number is smaller than any other. Another edge case is when nums contains the smallest or largest possible values, i.e., 0 and 100. The prefix sum array handles this without going out of bounds. A third edge case is when the array contains multiple duplicates interspersed with unique numbers. The prefix sum ensures each number correctly counts only strictly smaller numbers, not equal numbers. These edge cases demonstrate that the algorithm correctly handles boundaries, duplicates, and uniform arrays.