We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

How Many Numbers Are Smaller Than the Current Number

Number: 1482

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Yahoo, Accenture

Problem Description

Given an array nums, for each element nums[i] determine the number of elements in the array that are smaller than nums[i] (excluding itself). Return the resulting counts as an array.

Key Insights

  • The problem can be solved by counting how many numbers are smaller than a given number.
  • Since nums[i] is in the range 0 to 100, a counting sort technique is highly efficient.
  • A prefix sum array can be derived from the count array to quickly determine how many numbers are smaller than any given number.
  • This approach avoids a nested loop, reducing time complexity compared to a brute-force approach.

Space and Time Complexity

Time Complexity: O(n + k), where n is the number of elements and k is the range (101). Space Complexity: O(k) for the count/prefix array.

Solution

We first create a count array to record the frequency of each number from 0 to 100. We then use this count array to construct a prefix sum array, which indicates for any given number the total count of numbers that are less than it. Finally, for every element in the original array, we use the prefix sum array to retrieve the count of numbers smaller than that element. This approach leverages the constrained number range for efficient computation.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

def smallerNumbersThanCurrent(nums):
    # Initialize a count array for numbers 0 to 100.
    count = [0] * 101
    # Count the frequency of each number in the nums array.
    for num in nums:
        count[num] += 1
    # Build the prefix sum array.
    prefix = [0] * 101
    for i in range(1, 101):
        prefix[i] = prefix[i - 1] + count[i - 1]
    # For each number in nums, the corresponding prefix value represents the count of smaller numbers.
    result = []
    for num in nums:
        result.append(prefix[num])
    return result

# Example usage:
nums = [8, 1, 2, 2, 3]
print(smallerNumbersThanCurrent(nums))  # Output: [4, 0, 1, 1, 3]
← Back to All Questions