Jobs

Interviews

Discussions

Unique Number of Occurrences

Easy

Amazon

5 views

Topics:

Arrays

Given an array of integers arr, determine whether the number of occurrences of each value in the array is unique. Return true if the occurrences are unique, and false otherwise.

For example:

arr = [1, 2, 2, 1, 1, 3] should return true because 1 occurs 3 times, 2 occurs 2 times, and 3 occurs 1 time. These counts (3, 2, 1) are unique.
arr = [1, 2] should return false because 1 occurs 1 time and 2 occurs 1 time. The counts are not unique.
arr = [-3, 0, 1, -3, 1, 1, 1, -3, 10, 0] should return true because -3 occurs 3 times, 0 occurs 2 times, 1 occurs 4 times, and 10 occurs 1 time. These counts (3, 2, 4, 1) are unique.

Explain how you would approach this problem, considering the time and space complexity of your solution. Discuss any potential edge cases and provide code implementation in Python. The code should be well-commented and easy to understand.

Unique Number of Occurrences

Easy

Amazon

5 views

Topics:

Arrays

Given an array of integers arr, determine whether the number of occurrences of each value in the array is unique. Return true if the occurrences are unique, and false otherwise.

For example:

arr = [1, 2, 2, 1, 1, 3] should return true because 1 occurs 3 times, 2 occurs 2 times, and 3 occurs 1 time. These counts (3, 2, 1) are unique.
arr = [1, 2] should return false because 1 occurs 1 time and 2 occurs 1 time. The counts are not unique.
arr = [-3, 0, 1, -3, 1, 1, 1, -3, 10, 0] should return true because -3 occurs 3 times, 0 occurs 2 times, 1 occurs 4 times, and 10 occurs 1 time. These counts (3, 2, 4, 1) are unique.

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 within the input array?
Can the input array be empty or contain null values?
If the input array is empty, what should the function return?
Are we only dealing with integer values in the input array, or could there be other data types?
Are there any specific constraints on the size of the integers in the input array (e.g., can they exceed the maximum value of an integer)?

Brute Force Solution

Approach

The core idea is to count how many times each number appears in the list. After counting, we check if the counts themselves are all different. If they are, then the answer is yes; otherwise, it's no.

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

First, we need to figure out how many times each number shows up in the list.
So, for each number in the list, we go through the entire list again to count how many times that specific number appears.
After counting all the numbers, we have a list of the frequencies, telling us how often each unique number appears.
Then, we check if any of the counts are the same. We do this by looking at each count and comparing it to all the other counts.
If we find two counts that are the same, we know the answer is no. But if we go through all the counts and don't find any duplicates, then the answer is yes.

Code Implementation

def unique_occurrences_brute_force(numbers):
    frequency_list = []
    for number in numbers:
        count = 0
        for other_number in numbers:
            if number == other_number:
                count += 1
        frequency_list.append(count)

    # Convert frequency list to set to remove duplicate counts for accurate iteration
    unique_numbers = list(set(numbers))
    frequency_of_numbers = []

    for number in unique_numbers:
        count = 0
        for element in numbers:
            if number == element:
                count += 1
        frequency_of_numbers.append(count)

    # We must check each frequency against all other frequencies for uniqueness
    for i in range(len(frequency_of_numbers)):
        for j in range(i + 1, len(frequency_of_numbers)):

            # If duplicate frequencies are found, return false
            if frequency_of_numbers[i] == frequency_of_numbers[j]:
                return False

    return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n to count the occurrences of each number. For each of the n numbers, it iterates through the entire array again to calculate its frequency. Therefore, the number of operations is proportional to n multiplied by n. The algorithm then checks if any of the calculated frequencies are the same, which involves comparing each frequency with every other frequency, adding another nested loop that performs on the order of n squared operations. Consequently, the overall time complexity is O(n²).

Space Complexity

O(N) – The algorithm counts the frequency of each number in the input list. To store these frequencies, we effectively create a list of counts. In the worst-case scenario, where all N numbers in the input are unique, we would need to store N distinct counts. Therefore, the auxiliary space used to store the frequencies grows linearly with the input size N, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to determine if each number in a list appears a unique number of times. The most efficient way is to first count how many times each number appears and then check if those counts are all different.

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

First, we need to know how many times each number appears in the list. We can do this by going through the list and counting each number's occurrences.
Next, collect all the different counts we found in the previous step. For example, if '5' appears 3 times and '7' appears 3 times, then '3' would be added twice.
Finally, we'll check if all the counts in our collected counts are unique. If any count appears more than once, then we know the number of occurrences are not unique and return false. Otherwise, they are unique, and we return true.

Code Implementation

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

    # Use a set to efficiently check for duplicate counts
    counts_seen = set()
    for number in number_counts:

        count_of_number = number_counts[number]

        # If the current count already exists, there are duplicate occurrences.
        if count_of_number in counts_seen:
            return False

        counts_seen.add(count_of_number)

    # All occurrences are unique
    return True

Big(O) Analysis

Time Complexity

O(n) – The first step involves counting the occurrences of each number in the input list of size n. This can be done using a hash map (or dictionary), where we iterate through the list once. The second step involves creating a collection of the counts, which takes O(k) time, where k is the number of unique elements (k <= n). The final step involves checking for duplicate counts. Using a hash set, this also takes O(k) time. Because k is at most n, and all steps are either linear or constant time within a linear iteration, the overall time complexity is dominated by the initial linear iteration of the input list, leading to O(n).

Space Complexity

O(N) – The algorithm uses a hash map to count the occurrences of each number in the input list. In the worst-case scenario, where all N numbers in the input list are unique, the hash map will store N key-value pairs. Additionally, a set is used to store the counts to check for uniqueness, and in the worst case, it will also store N distinct counts. Thus, the auxiliary space used is proportional to N, giving a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return true since an empty array trivially satisfies the condition of unique occurrences.
Array with a single element	Return true as a single element has a unique occurrence count of 1.
Array with all elements being the same value	The occurrence count will be equal to the array's size; check if the frequency map already contains that number.
Array with maximum integer values	Using a HashMap or frequency array can still accommodate large integer values, given sufficient memory.
Integer overflow in frequency counts	Use a data type large enough to accommodate potential maximum frequency (e.g., long in Java) or check for overflows.
Large input array size (scalability)	A HashMap approach provides O(n) time complexity, which scales reasonably well.
Negative numbers in the input array	HashMaps can handle negative numbers as keys without any special treatment.
Extreme difference in frequency counts between elements	This should not cause any issues as we iterate through the frequency map once and use a set to ensure uniqueness, so the solution is independent of frequency count value.

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 within the input array?
Can the input array be empty or contain null values?
If the input array is empty, what should the function return?
Are we only dealing with integer values in the input array, or could there be other data types?
Are there any specific constraints on the size of the integers in the input array (e.g., can they exceed the maximum value of an integer)?

Brute Force Solution

Approach

The core idea is to count how many times each number appears in the list. After counting, we check if the counts themselves are all different. If they are, then the answer is yes; otherwise, it's no.

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

First, we need to figure out how many times each number shows up in the list.
So, for each number in the list, we go through the entire list again to count how many times that specific number appears.
After counting all the numbers, we have a list of the frequencies, telling us how often each unique number appears.
Then, we check if any of the counts are the same. We do this by looking at each count and comparing it to all the other counts.
If we find two counts that are the same, we know the answer is no. But if we go through all the counts and don't find any duplicates, then the answer is yes.

Code Implementation

def unique_occurrences_brute_force(numbers):
    frequency_list = []
    for number in numbers:
        count = 0
        for other_number in numbers:
            if number == other_number:
                count += 1
        frequency_list.append(count)

    # Convert frequency list to set to remove duplicate counts for accurate iteration
    unique_numbers = list(set(numbers))
    frequency_of_numbers = []

    for number in unique_numbers:
        count = 0
        for element in numbers:
            if number == element:
                count += 1
        frequency_of_numbers.append(count)

    # We must check each frequency against all other frequencies for uniqueness
    for i in range(len(frequency_of_numbers)):
        for j in range(i + 1, len(frequency_of_numbers)):

            # If duplicate frequencies are found, return false
            if frequency_of_numbers[i] == frequency_of_numbers[j]:
                return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, we need to know how many times each number appears in the list. We can do this by going through the list and counting each number's occurrences.
Next, collect all the different counts we found in the previous step. For example, if '5' appears 3 times and '7' appears 3 times, then '3' would be added twice.
Finally, we'll check if all the counts in our collected counts are unique. If any count appears more than once, then we know the number of occurrences are not unique and return false. Otherwise, they are unique, and we return true.

Code Implementation

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

    # Use a set to efficiently check for duplicate counts
    counts_seen = set()
    for number in number_counts:

        count_of_number = number_counts[number]

        # If the current count already exists, there are duplicate occurrences.
        if count_of_number in counts_seen:
            return False

        counts_seen.add(count_of_number)

    # All occurrences are unique
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return true since an empty array trivially satisfies the condition of unique occurrences.
Array with a single element	Return true as a single element has a unique occurrence count of 1.
Array with all elements being the same value	The occurrence count will be equal to the array's size; check if the frequency map already contains that number.
Array with maximum integer values	Using a HashMap or frequency array can still accommodate large integer values, given sufficient memory.
Integer overflow in frequency counts	Use a data type large enough to accommodate potential maximum frequency (e.g., long in Java) or check for overflows.
Large input array size (scalability)	A HashMap approach provides O(n) time complexity, which scales reasonably well.
Negative numbers in the input array	HashMaps can handle negative numbers as keys without any special treatment.
Extreme difference in frequency counts between elements	This should not cause any issues as we iterate through the frequency map once and use a set to ensure uniqueness, so the solution is independent of frequency count value.