Jobs

Interviews

Discussions

Find All Lonely Numbers in the Array

Medium

Google

3 views

Topics:

Arrays

You are given an integer array nums. A number x is lonely when it appears only once, and no adjacent numbers (i.e. x + 1 and x - 1) appear in the array.

Write a function to return all lonely numbers in nums. You may return the answer in any order.

For example:

findLonely([10,6,5,8]) should return [10,8] because:

10 is a lonely number since it appears exactly once and 9 and 11 do not appear in nums.
8 is a lonely number since it appears exactly once and 7 and 9 do not appear in nums.
5 is not a lonely number since 6 appears in nums and vice versa.

findLonely([1,3,5,3]) should return [1,5] because:

1 is a lonely number since it appears exactly once and 0 and 2 do not appear in nums.
5 is a lonely number since it appears exactly once and 4 and 6 do not appear in nums.
3 is not a lonely number since it appears twice.

Consider the time and space complexity of your solution. Can you optimize it?

Find All Lonely Numbers in the Array

Medium

Google

3 views

Topics:

Arrays

You are given an integer array nums. A number x is lonely when it appears only once, and no adjacent numbers (i.e. x + 1 and x - 1) appear in the array.

Write a function to return all lonely numbers in nums. You may return the answer in any order.

For example:

findLonely([10,6,5,8]) should return [10,8] because:

10 is a lonely number since it appears exactly once and 9 and 11 do not appear in nums.
8 is a lonely number since it appears exactly once and 7 and 9 do not appear in nums.
5 is not a lonely number since 6 appears in nums and vice versa.

findLonely([1,3,5,3]) should return [1,5] because:

1 is a lonely number since it appears exactly once and 0 and 2 do not appear in nums.
5 is a lonely number since it appears exactly once and 4 and 6 do not appear in nums.
3 is not a lonely number since it appears twice.

Consider the time and space complexity of your solution. Can you optimize it?

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 possible values for the integers in the array?
Can the input array be empty or null? If so, what should I return?
Does the order of the lonely numbers in the output matter, or can they be in any order?
Can the input array contain duplicate numbers that are not 'lonely'? For example, if the input is `[1, 1, 2, 3]`, is `2` a lonely number?
By 'adjacent' do you mean 'immediately' adjacent? Meaning, if the input is `[1, 3, 5]` is 3 considered lonely?

Brute Force Solution

Approach

The brute force method for finding lonely numbers is all about checking every single number to see if it's lonely. We'll consider each number one at a time and look through the rest of the numbers to make sure there are no close neighbors.

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

Take the first number from the group.
Now, look at every other number in the group.
For each of those other numbers, check if it is one less or one more than the first number we took.
If we find a number that is one less or one more, then the first number is not lonely, so we can move on.
If we check all the other numbers and don't find any that are one less or one more, then the first number is lonely and we should remember it.
Repeat this process for every number in the group, making sure to compare it with all the other numbers.
At the end, we will have a list of all the lonely numbers we found.

Code Implementation

def find_all_lonely_numbers_brute_force(numbers):
    lonely_numbers = []
    number_of_elements = len(numbers)

    for i in range(number_of_elements):
        is_lonely = True
        current_number = numbers[i]

        # Compare current number with all others
        for j in range(number_of_elements):
            if i == j:
                continue

            other_number = numbers[j]

            # Check for neighbors
            if other_number == current_number - 1 or other_number == current_number + 1:
                is_lonely = False
                break

        # If no neighbors found, number is lonely
        if is_lonely:
            lonely_numbers.append(current_number)

    return lonely_numbers

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through each of the n numbers in the input array. For each number, it then iterates through the remaining n-1 numbers to check if any of them are adjacent (differ by 1). This nested iteration results in approximately n * (n-1) comparisons. Simplifying this expression removes the lower order terms and constant factors. Thus, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force approach iterates through the input array without creating any auxiliary data structures that scale with the input size N. It only uses a few variables for indices and comparisons. The algorithm iterates through the array to compare each number with the rest, but it doesn't store intermediate results in additional arrays or hash maps. Therefore, the space complexity is constant, independent of the input size N.

Optimal Solution

Approach

To find lonely numbers quickly, we can count how often each number appears. A lonely number appears exactly once. We can then go through the original list and identify the numbers that appeared only once in our count.

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

First, we need a way to count how many times each number shows up in the list.
Then, we go through the list again. For each number, we check its count.
If the count is exactly one, that means the number is lonely, so we add it to our list of lonely numbers.
Finally, we return the list of lonely numbers we found.

Code Implementation

def find_lonely(number_list):
    number_counts = {}

    # Count the occurrences of each number
    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    lonely_numbers = []

    # We need to iterate to find all lonely numbers.
    for number in number_list:
        if number_counts[number] == 1:

            # A lonely number exists if its count is 1.
            lonely_numbers.append(number)

    # We must sort the result as per requirements.
    lonely_numbers.sort()
    return lonely_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm first counts the frequency of each number in the input array of size n. This operation requires iterating through the array once, which takes O(n) time. Then, it iterates through the array again to identify lonely numbers based on their frequency. This second iteration also takes O(n) time. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The primary auxiliary space is used by the count of each number, which can be implemented using a hash map or dictionary. In the worst-case scenario, where all numbers in the input array of size N are unique, the hash map will need to store N key-value pairs, where each key is a number from the input and the value is its count. Therefore, the auxiliary space required grows linearly with the number of elements in the input array. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list since there are no numbers to evaluate.
Array with only one element	Return the array itself as the single element is considered lonely by definition.
Array with all identical numbers	Return an empty list because no number can be lonely.
Large input array causing potential memory issues	Use a memory-efficient data structure like a hash map or set and optimize algorithm for constant space where possible.
Array containing negative numbers	The solution should correctly handle negative numbers without any modification as long as the core logic remains unchanged.
Array containing zero	The solution should function correctly with zero as any other number.
Integer overflow if numbers are extremely large	Consider using a larger data type (e.g., long) or appropriate modular arithmetic if the problem defines a range and overflow is possible.
Input array is already sorted.	The algorithm should still function correctly; consider optimizing by using sorted array properties if possible, but not required.

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 possible values for the integers in the array?
Can the input array be empty or null? If so, what should I return?
Does the order of the lonely numbers in the output matter, or can they be in any order?
Can the input array contain duplicate numbers that are not 'lonely'? For example, if the input is `[1, 1, 2, 3]`, is `2` a lonely number?
By 'adjacent' do you mean 'immediately' adjacent? Meaning, if the input is `[1, 3, 5]` is 3 considered lonely?

Brute Force Solution

Approach

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

Take the first number from the group.
Now, look at every other number in the group.
For each of those other numbers, check if it is one less or one more than the first number we took.
If we find a number that is one less or one more, then the first number is not lonely, so we can move on.
If we check all the other numbers and don't find any that are one less or one more, then the first number is lonely and we should remember it.
Repeat this process for every number in the group, making sure to compare it with all the other numbers.
At the end, we will have a list of all the lonely numbers we found.

Code Implementation

def find_all_lonely_numbers_brute_force(numbers):
    lonely_numbers = []
    number_of_elements = len(numbers)

    for i in range(number_of_elements):
        is_lonely = True
        current_number = numbers[i]

        # Compare current number with all others
        for j in range(number_of_elements):
            if i == j:
                continue

            other_number = numbers[j]

            # Check for neighbors
            if other_number == current_number - 1 or other_number == current_number + 1:
                is_lonely = False
                break

        # If no neighbors found, number is lonely
        if is_lonely:
            lonely_numbers.append(current_number)

    return lonely_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, we need a way to count how many times each number shows up in the list.
Then, we go through the list again. For each number, we check its count.
If the count is exactly one, that means the number is lonely, so we add it to our list of lonely numbers.
Finally, we return the list of lonely numbers we found.

Code Implementation

def find_lonely(number_list):
    number_counts = {}

    # Count the occurrences of each number
    for number in number_list:
        number_counts[number] = number_counts.get(number, 0) + 1

    lonely_numbers = []

    # We need to iterate to find all lonely numbers.
    for number in number_list:
        if number_counts[number] == 1:

            # A lonely number exists if its count is 1.
            lonely_numbers.append(number)

    # We must sort the result as per requirements.
    lonely_numbers.sort()
    return lonely_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty list since there are no numbers to evaluate.
Array with only one element	Return the array itself as the single element is considered lonely by definition.
Array with all identical numbers	Return an empty list because no number can be lonely.
Large input array causing potential memory issues	Use a memory-efficient data structure like a hash map or set and optimize algorithm for constant space where possible.
Array containing negative numbers	The solution should correctly handle negative numbers without any modification as long as the core logic remains unchanged.
Array containing zero	The solution should function correctly with zero as any other number.
Integer overflow if numbers are extremely large	Consider using a larger data type (e.g., long) or appropriate modular arithmetic if the problem defines a range and overflow is possible.
Input array is already sorted.	The algorithm should still function correctly; consider optimizing by using sorted array properties if possible, but not required.