Leetcode – How Many Numbers Are Smaller Than the Current Number Solution

Spread the love

The problem “How Many Numbers Are Smaller Than the Current Number” is an excellent starting point for those who are new to algorithmic problem-solving or for experienced coders who want to brush up on their basics. This problem appears on Leetcode and serves as a basis for understanding more complex algorithms and data structures like sorting and hash tables.

In this comprehensive guide, we will discuss the problem statement, different approaches to solving it, and the pros and cons of each approach. We’ll also examine various Python code implementations, explaining each line in detail.

Problem Statement

The problem asks you to find out how many numbers in an array are smaller than each number in that array. More formally, for every number nums[i], you have to count the number of elements in nums that are smaller than nums[i] and store that count at index i in the result array.

Constraints:

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

Example

Input: [8, 1, 2, 2, 3]
Output: [4, 0, 1, 1, 3]

In the example, the number 8 is greater than four other numbers in the list, the number 1 is greater than zero other numbers, the number 2 is greater than one other number, and so on.

Approaches to Solve the Problem

Brute Force Approach

The most straightforward approach to solving this problem is to use two nested loops to compare each element with every other element.

Here’s the Python code snippet for the brute-force approach:

def smallerNumbersThanCurrent(nums):
    result = []
    for i in range(len(nums)):
        count = 0
        for j in range(len(nums)):
            if i != j and nums[j] < nums[i]:
                count += 1
        result.append(count)
    return result

Time Complexity: O(n^2)

Space Complexity: O(1) (not counting the output array)

Sorting and Dictionary Approach

A more efficient way to solve this problem involves sorting the array and using a dictionary to keep track of the elements that are smaller than the current number.

Here’s the Python code snippet:

def smallerNumbersThanCurrent(nums):
    sorted_nums = sorted(nums)
    count_dict = {}
    
    for i, n in enumerate(sorted_nums):
        if n not in count_dict:
            count_dict[n] = i
            
    return [count_dict[n] for n in nums]

Time Complexity: O(n log ⁡n)

Space Complexity: O(n)

Counting Sort Approach

Since the constraints specify that nums[i] <= 100, we can also solve this problem using counting sort for an even more optimized solution.

Here’s the Python code snippet:

def smallerNumbersThanCurrent(nums):
    count = [0] * 101
    for num in nums:
        count[num] += 1
    
    for i in range(1, 101):
        count[i] += count[i - 1]
        
    return [count[num - 1] if num else 0 for num in nums]

Time Complexity: O(n)

Space Complexity: O(n)

Comparison of Approaches

Brute-Force

  • Pros: Easy to understand and implement.
  • Cons: Least efficient. Not practical for large inputs.

Sorting and Dictionary

  • Pros: More efficient than the brute-force method. Easy to understand.
  • Cons: Uses extra memory for sorting and dictionary.

Counting Sort

  • Pros: Most efficient, especially for a small range of integers.
  • Cons: Limited to integer arrays and relies on knowing the maximum value beforehand.

Conclusion

The problem “How Many Numbers Are Smaller Than the Current Number” provides a fertile ground for understanding basic algorithmic concepts such as sorting and hash tables. It also showcases how different algorithms can be more or less suitable depending on the constraints of the problem.

We have discussed three different approaches—brute-force, sorting with dictionary, and counting sort—each with its own set of advantages and disadvantages. Depending on your specific needs and constraints, you can pick the one that’s most appropriate for you.

Leave a Reply