Jobs

Interviews

Discussions

How Many Numbers Are Smaller Than the Current Number

Easy

Google

1 view

Topics:

Arrays

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

For example:

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

output = [4, 0, 1, 1, 3]

Explanation:

For nums[0] = 8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1] = 1 does not exist any smaller number than it.
For nums[2] = 2 there exist one smaller number than it (1).
For nums[3] = 2 there exist one smaller number than it (1).
For nums[4] = 3 there exist three smaller numbers than it (1, 2 and 2).

How would you efficiently solve this problem, taking into consideration time and space complexity. What are the edge cases to consider?

How Many Numbers Are Smaller Than the Current Number

Easy

Google

1 view

Topics:

Arrays

Return the answer in an array.

For example:

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

output = [4, 0, 1, 1, 3]

Explanation:

For nums[0] = 8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1] = 1 does not exist any smaller number than it.
For nums[2] = 2 there exist one smaller number than it (1).
For nums[3] = 2 there exist one smaller number than it (1).
For nums[4] = 3 there exist three smaller numbers than it (1, 2 and 2).

How would you efficiently solve this problem, taking into consideration time and space complexity. What are the edge cases to consider?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the input array? Can I assume they are integers?
Can the input array be empty or null? If so, what should I return?
Does the order of the output correspond to the order of the input numbers?
Are duplicate numbers in the input array allowed? If so, how should they be handled when counting smaller numbers?
How large can the input array be?

Brute Force Solution

Approach

The brute force approach solves this by directly comparing each number to every other number. We count how many numbers in the list are smaller than the current number we are looking at. We repeat this process for each number in the list.

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Compare this number to every other number in the list.
Count how many of the other numbers are smaller than the first number.
Write down this count as the answer for the first number.
Now, take the second number from the list.
Compare this number to every other number in the list (including the first number).
Count how many of the other numbers are smaller than the second number.
Write down this count as the answer for the second number.
Continue this process for each number in the list.
After checking all numbers, you will have a list of counts, with each count representing how many numbers are smaller than the corresponding number in the original list.

Code Implementation

def how_many_smaller(numbers):
    result_list = []
    
    # Iterate through each number in the input list
    for current_number_index in range(len(numbers)):
        current_number = numbers[current_number_index]
        smaller_count = 0
        
        # Compare the current number with every other number in the list
        for other_number_index in range(len(numbers)):
            # We only count if the other number is smaller
            if numbers[other_number_index] < current_number:

                smaller_count += 1
        
        result_list.append(smaller_count)
        
    return result_list

Big(O) Analysis

Time Complexity

O(n²) – The brute force approach iterates through each element of the input array of size n. For each element, it compares it to every other element in the array to count how many are smaller. Therefore, for each of the n elements, we perform approximately n comparisons. This results in approximately n * n operations, which simplifies to a time complexity of O(n²).

Space Complexity

O(1) – The provided algorithm only uses a few constant space variables such as loop counters or temporary storage for comparisons. It doesn't create any auxiliary data structures whose size depends on the input. Therefore, the auxiliary space complexity is constant, or O(1), as it does not scale with the input size N.

Optimal Solution

Approach

The efficient approach avoids direct comparison. It smartly counts the number of elements smaller than each number in a given list without checking every number against all the others.

Here's how the algorithm would work step-by-step:

First, figure out how many times each unique number appears in the list. Basically count them up and keep track of how many of each number there are.
Next, find the smallest number in the list and remember that zero numbers are smaller than it.
Then, go through the unique numbers in sorted order. For each number, add up the counts of all the smaller numbers you've seen before. This total will be the number of elements smaller than the current number.
Finally, for each number in the original list, look up how many numbers were smaller than it, using the information you just gathered in the previous step. Return those counts.

Code Implementation

def how_many_smaller_numbers(number_list):
    number_counts = {}
    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    smaller_counts = {}
    sorted_numbers = sorted(number_counts.keys())
    
    # The smallest number has zero smaller numbers
    smaller_count = 0
    for number in sorted_numbers:
        smaller_counts[number] = smaller_count

        # Accumulate the counts of smaller numbers
        smaller_count += number_counts[number]

    result_list = []
    # Look up the smaller counts for each number
    for number in number_list:
        result_list.append(smaller_counts[number])

    return result_list

Big(O) Analysis

Time Complexity

O(n + klogk) – The initial counting of element frequencies takes O(n) time, where n is the length of the input array. Sorting the unique numbers, where k is the number of unique numbers (k <= n), takes O(klogk) time. Calculating the cumulative counts of smaller numbers iterates through the unique numbers once, taking O(k) time. Finally, looking up the counts for each element in the original array takes O(n) time. Since k <= n, the dominant term is n + klogk.

Space Complexity

O(N) – The algorithm uses a hash map (or similar data structure) to count the occurrences of each unique number in the list. In the worst case, where all numbers are unique, this hash map will store N key-value pairs, where N is the number of elements in the input list. An additional data structure (likely a list or array) is needed to store the counts of numbers smaller than the current number for each value in the original list, contributing another O(N) space requirement. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array since there are no numbers to compare.
Array with a single element	Return an array containing only zero, since there are no other elements to be smaller than it.
Array with all identical numbers	Return an array filled with zeros, as no number is smaller than any other.
Array with very large numbers (close to integer limits)	Ensure integer overflow does not occur during counting; consider using a larger data type if necessary.
Array with negative numbers	The solution should correctly compare and count negative numbers against each other and positive numbers.
Array with duplicate numbers and zero	The counting mechanism must accurately reflect counts even when duplicates or zeros are present.
Extremely large array (potential memory issues)	The solution should consider memory usage; using sorting based approaches might have implications on large input sizes.
Array contains a large range of numbers, requiring a big bucket array in counting sort	Adjust bucket size in counting sort, or prefer an alternative solution (sorting based approach) when range is too large.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values in the input array? Can I assume they are integers?
Can the input array be empty or null? If so, what should I return?
Does the order of the output correspond to the order of the input numbers?
Are duplicate numbers in the input array allowed? If so, how should they be handled when counting smaller numbers?
How large can the input array be?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Compare this number to every other number in the list.
Count how many of the other numbers are smaller than the first number.
Write down this count as the answer for the first number.
Now, take the second number from the list.
Compare this number to every other number in the list (including the first number).
Count how many of the other numbers are smaller than the second number.
Write down this count as the answer for the second number.
Continue this process for each number in the list.
After checking all numbers, you will have a list of counts, with each count representing how many numbers are smaller than the corresponding number in the original list.

Code Implementation

def how_many_smaller(numbers):
    result_list = []
    
    # Iterate through each number in the input list
    for current_number_index in range(len(numbers)):
        current_number = numbers[current_number_index]
        smaller_count = 0
        
        # Compare the current number with every other number in the list
        for other_number_index in range(len(numbers)):
            # We only count if the other number is smaller
            if numbers[other_number_index] < current_number:

                smaller_count += 1
        
        result_list.append(smaller_count)
        
    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The efficient approach avoids direct comparison. It smartly counts the number of elements smaller than each number in a given list without checking every number against all the others.

Here's how the algorithm would work step-by-step:

First, figure out how many times each unique number appears in the list. Basically count them up and keep track of how many of each number there are.
Next, find the smallest number in the list and remember that zero numbers are smaller than it.
Then, go through the unique numbers in sorted order. For each number, add up the counts of all the smaller numbers you've seen before. This total will be the number of elements smaller than the current number.
Finally, for each number in the original list, look up how many numbers were smaller than it, using the information you just gathered in the previous step. Return those counts.

Code Implementation

def how_many_smaller_numbers(number_list):
    number_counts = {}
    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    smaller_counts = {}
    sorted_numbers = sorted(number_counts.keys())
    
    # The smallest number has zero smaller numbers
    smaller_count = 0
    for number in sorted_numbers:
        smaller_counts[number] = smaller_count

        # Accumulate the counts of smaller numbers
        smaller_count += number_counts[number]

    result_list = []
    # Look up the smaller counts for each number
    for number in number_list:
        result_list.append(smaller_counts[number])

    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array since there are no numbers to compare.
Array with a single element	Return an array containing only zero, since there are no other elements to be smaller than it.
Array with all identical numbers	Return an array filled with zeros, as no number is smaller than any other.
Array with very large numbers (close to integer limits)	Ensure integer overflow does not occur during counting; consider using a larger data type if necessary.
Array with negative numbers	The solution should correctly compare and count negative numbers against each other and positive numbers.
Array with duplicate numbers and zero	The counting mechanism must accurately reflect counts even when duplicates or zeros are present.
Extremely large array (potential memory issues)	The solution should consider memory usage; using sorting based approaches might have implications on large input sizes.
Array contains a large range of numbers, requiring a big bucket array in counting sort	Adjust bucket size in counting sort, or prefer an alternative solution (sorting based approach) when range is too large.