Jobs

Interviews

Discussions

Count of Smaller Numbers After Self

Hard

Apple

2 views

Topics:

ArraysBinary Search

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

For example:

nums = [5,2,6,1] should return [2,1,1,0] because:
- To the right of 5 there are 2 smaller elements (2 and 1).
- To the right of 2 there is only 1 smaller element (1).
- To the right of 6 there is 1 smaller element (1).
- To the right of 1 there are 0 smaller elements.
nums = [-1] should return [0]
nums = [-1,-1] should return [0,0]

Write a function to solve this problem efficiently. Consider the time and space complexity of your solution. How does your solution handle edge cases like empty arrays or arrays with duplicate elements?

Count of Smaller Numbers After Self

Hard

Apple

2 views

Topics:

ArraysBinary Search

Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].

For example:

nums = [5,2,6,1] should return [2,1,1,0] because:
- To the right of 5 there are 2 smaller elements (2 and 1).
- To the right of 2 there is only 1 smaller element (1).
- To the right of 6 there is 1 smaller element (1).
- To the right of 1 there are 0 smaller elements.
nums = [-1] should return [0]
nums = [-1,-1] should return [0,0]

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 for the numbers in the input array?
Can the input array contain duplicate numbers, and if so, how should they be handled in determining the count of smaller numbers?
What should be returned if the input array is null or empty?
Is the order of the output array significant? Should the counts correspond to the order of the input array?
Can you provide an example of the input and the expected output to ensure I understand the problem correctly?

Brute Force Solution

Approach

The goal is to figure out, for each number in a list, how many numbers to its right are smaller. The brute force way to do this is to simply check every number to the right of each number, one at a time.

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

For the very first number in the list, look at every number that comes after it.
For each of those numbers to the right, check if it is smaller than the first number.
Count how many numbers to the right are smaller. That's the answer for the first number.
Now, move to the second number in the list and do the exact same thing.
Look at every number to the right of the second number.
Check if each of those numbers is smaller than the second number.
Count how many numbers to the right are smaller. That's the answer for the second number.
Keep doing this for every number in the list. For each number, you're always comparing it to every number that comes later in the list.
In the end, you'll have a list of counts, where each count tells you how many smaller numbers are to the right of the corresponding number in the original list.

Code Implementation

def count_smaller_numbers_after_self_brute_force(numbers):
    counts = []

    # Iterate through each number in the input list
    for index in range(len(numbers)):
        smaller_count = 0

        # Compare the current number with all numbers to its right
        for comparison_index in range(index + 1, len(numbers)):

            # Count smaller numbers
            if numbers[comparison_index] < numbers[index]:
                smaller_count += 1

        counts.append(smaller_count)

    return counts

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the input list. For each element, it then iterates through the remaining elements to its right to count how many are smaller. In the worst case, for the first element, we compare with n-1 elements, for the second with n-2 elements, and so on down to the last. This results in roughly n*(n-1)/2 comparisons which simplifies to O(n²).

Space Complexity

O(1) – The provided algorithm iterates through the input list, comparing each element to the elements to its right. It doesn't create any auxiliary data structures like temporary lists or hash maps to store intermediate results. The space used is limited to a few variables for indexing and counting, which remains constant irrespective of the input list's size, N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to process the numbers from right to left, maintaining a sorted collection of the numbers we've already seen. As we encounter each new number, we can efficiently determine how many numbers in our sorted collection are smaller than it.

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

Begin by looking at the very last number in the original list.
Create a new sorted list, and initially put only that last number into it.
Now, move to the second to last number in the original list.
Figure out where this new number would fit in the sorted list, keeping the sorted order correct. The number of items *before* this position in the sorted list tells us how many numbers to the right of it in the original list are smaller than this number.
Add this new number into the sorted list at the right spot.
Repeat this process, moving from right to left across all the numbers in the original list.
Each time, insert the current number into the correct position in the sorted list, and record the count of smaller numbers. The count of smaller numbers represents the number of elements smaller than the current element in the sorted data structure.
The result is a list containing, for each number in the original list, the count of smaller numbers to its right.

Code Implementation

def count_of_smaller_numbers_after_self(numbers):
    result = []
    sorted_list = []

    for i in range(len(numbers) - 1, -1, -1):
        number = numbers[i]
        count = 0
        insert_position = 0

        # Find the correct insertion position to maintain the sorted order
        for j in range(len(sorted_list)): 
            if sorted_list[j] < number:
                insert_position += 1
            else:
                break

        # Store number of smaller elements to the right
        result.insert(0, insert_position)

        #Insert number at the right position in the sorted list
        sorted_list.insert(insert_position, number)

    return result

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n from right to left. In each iteration, it inserts the current element into a sorted list using a method that requires finding the correct insertion point. Finding this insertion point takes O(n) time in the worst case because we might have to scan the entire sorted list. Since this insertion process is repeated for each of the n elements, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm maintains a sorted list to store the numbers encountered so far while traversing the input list from right to left. In the worst-case scenario, this sorted list will contain all N elements of the original input list. Therefore, the auxiliary space required for this sorted list grows linearly with the input size N. No other significant auxiliary space is used beyond this list, hence the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately to avoid null pointer exceptions or errors from processing an empty sequence.
Array with a single element	Return a list containing a single 0, as there are no elements after the single element.
Array with all identical elements	Return a list of all zeros, as no element is smaller than any element after it.
Array with numbers in strictly increasing order	Return a list of all zeros, as no element is smaller than any element after it.
Array with numbers in strictly decreasing order	The i-th element in the output list will be equal to (n-1-i), representing the number of smaller elements that come after the i-th element.
Array containing large positive and negative numbers	Ensure the comparison logic handles negative numbers correctly and the range of integers does not cause overflow issues in the chosen algorithm.
Maximum size input array (performance considerations)	Consider using a data structure like a balanced binary search tree (e.g., AVL tree, Red-Black tree) or a merge sort based approach to maintain logarithmic time complexity for insertion and querying, ensuring the algorithm scales well to large inputs.
Presence of zero(s) in the input array	The comparison logic should correctly identify elements smaller than zero and count them appropriately.

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 for the numbers in the input array?
Can the input array contain duplicate numbers, and if so, how should they be handled in determining the count of smaller numbers?
What should be returned if the input array is null or empty?
Is the order of the output array significant? Should the counts correspond to the order of the input array?
Can you provide an example of the input and the expected output to ensure I understand the problem correctly?

Brute Force Solution

Approach

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

For the very first number in the list, look at every number that comes after it.
For each of those numbers to the right, check if it is smaller than the first number.
Count how many numbers to the right are smaller. That's the answer for the first number.
Now, move to the second number in the list and do the exact same thing.
Look at every number to the right of the second number.
Check if each of those numbers is smaller than the second number.
Count how many numbers to the right are smaller. That's the answer for the second number.
Keep doing this for every number in the list. For each number, you're always comparing it to every number that comes later in the list.
In the end, you'll have a list of counts, where each count tells you how many smaller numbers are to the right of the corresponding number in the original list.

Code Implementation

def count_smaller_numbers_after_self_brute_force(numbers):
    counts = []

    # Iterate through each number in the input list
    for index in range(len(numbers)):
        smaller_count = 0

        # Compare the current number with all numbers to its right
        for comparison_index in range(index + 1, len(numbers)):

            # Count smaller numbers
            if numbers[comparison_index] < numbers[index]:
                smaller_count += 1

        counts.append(smaller_count)

    return counts

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Begin by looking at the very last number in the original list.
Create a new sorted list, and initially put only that last number into it.
Now, move to the second to last number in the original list.
Figure out where this new number would fit in the sorted list, keeping the sorted order correct. The number of items *before* this position in the sorted list tells us how many numbers to the right of it in the original list are smaller than this number.
Add this new number into the sorted list at the right spot.
Repeat this process, moving from right to left across all the numbers in the original list.
Each time, insert the current number into the correct position in the sorted list, and record the count of smaller numbers. The count of smaller numbers represents the number of elements smaller than the current element in the sorted data structure.
The result is a list containing, for each number in the original list, the count of smaller numbers to its right.

Code Implementation

def count_of_smaller_numbers_after_self(numbers):
    result = []
    sorted_list = []

    for i in range(len(numbers) - 1, -1, -1):
        number = numbers[i]
        count = 0
        insert_position = 0

        # Find the correct insertion position to maintain the sorted order
        for j in range(len(sorted_list)): 
            if sorted_list[j] < number:
                insert_position += 1
            else:
                break

        # Store number of smaller elements to the right
        result.insert(0, insert_position)

        #Insert number at the right position in the sorted list
        sorted_list.insert(insert_position, number)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list immediately to avoid null pointer exceptions or errors from processing an empty sequence.
Array with a single element	Return a list containing a single 0, as there are no elements after the single element.
Array with all identical elements	Return a list of all zeros, as no element is smaller than any element after it.
Array with numbers in strictly increasing order	Return a list of all zeros, as no element is smaller than any element after it.
Array with numbers in strictly decreasing order	The i-th element in the output list will be equal to (n-1-i), representing the number of smaller elements that come after the i-th element.
Array containing large positive and negative numbers	Ensure the comparison logic handles negative numbers correctly and the range of integers does not cause overflow issues in the chosen algorithm.
Maximum size input array (performance considerations)	Consider using a data structure like a balanced binary search tree (e.g., AVL tree, Red-Black tree) or a merge sort based approach to maintain logarithmic time complexity for insertion and querying, ensuring the algorithm scales well to large inputs.
Presence of zero(s) in the input array	The comparison logic should correctly identify elements smaller than zero and count them appropriately.