Problem Description

You are given an integer array nums. A number x is considered lonely when it meets two conditions:

1. It appears exactly once in the array (frequency of 1)
2. Its adjacent numbers (x - 1 and x + 1) do not appear in the array at all

Your task is to find and return all lonely numbers in nums. The numbers can be returned in any order.

For example, if nums = [10, 6, 5, 8], then:

• 10 is lonely because it appears once, and neither 9 nor 11 appear in the array
• 6 is NOT lonely because although it appears once, 5 (which is 6 - 1) also appears in the array
• 5 is NOT lonely because 6 (which is 5 + 1) appears in the array
• 8 is lonely because it appears once, and neither 7 nor 9 appear in the array

So the answer would be [10, 8].

The solution uses a hash table (Counter) to track the frequency of each number, then filters for numbers that appear exactly once and have no adjacent numbers present in the array.

Intuition

To identify lonely numbers, we need to check two conditions for each number: whether it appears exactly once, and whether its adjacent numbers (x - 1 and x + 1) are absent from the array.

The key insight is that we need to know the frequency of every number in the array before we can determine if any number is lonely. This naturally leads us to use a frequency counting approach.

Why a hash table? Consider checking if a number x is lonely:

• We need to know if x appears exactly once
• We need to know if x - 1 exists in the array
• We need to know if x + 1 exists in the array

Without preprocessing, we'd have to scan the entire array three times for each number we check, resulting in O(n²) time complexity.

By using a hash table (Counter) to store frequencies first, we can answer all three questions in O(1) time for each number. The Counter gives us both the frequency information and acts as a set to check existence - if a number doesn't exist in the Counter, its count is implicitly 0.

Once we have the frequency map, we simply iterate through it and check each number against our lonely criteria: count[x] == 1 and count[x-1] == 0 and count[x+1] == 0. This gives us an efficient O(n) solution overall.

Solution Approach

The solution uses a hash table to efficiently track the occurrence count of each number and check for adjacent numbers.

Step 1: Count Frequencies We use Python's Counter from the collections module to create a hash table cnt that stores the frequency of each number in the array:

cnt = Counter(nums)

This gives us a dictionary where keys are the numbers from nums and values are their occurrence counts.

Step 2: Filter Lonely Numbers We iterate through the hash table using a list comprehension to find all lonely numbers:

return [
    x for x, v in cnt.items() if v == 1 and cnt[x - 1] == 0 and cnt[x + 1] == 0
]

For each number x with frequency v in the hash table, we check three conditions:

• v == 1: The number appears exactly once
• cnt[x - 1] == 0: The number x - 1 doesn't exist in the array (Counter returns 0 for non-existent keys)
• cnt[x + 1] == 0: The number x + 1 doesn't exist in the array

Only numbers that satisfy all three conditions are included in the result.

Time Complexity: O(n) where n is the length of the input array. We iterate through the array once to build the Counter, and then iterate through the unique numbers once to check the lonely conditions.

Space Complexity: O(n) for storing the hash table, which in the worst case contains all unique numbers from the input array.

Example Walkthrough

Let's walk through the solution with nums = [1, 3, 5, 3].

Step 1: Build the frequency map

First, we create a Counter to track how many times each number appears:

cnt = Counter([1, 3, 5, 3])
cnt = {1: 1, 3: 2, 5: 1}

Step 2: Check each number for loneliness

Now we examine each unique number in our frequency map:

For x = 1 (frequency = 1):

• Does 1 appear exactly once? ✓ Yes (frequency = 1)
• Is x - 1 = 0 absent from the array? ✓ Yes (cnt[0] = 0)
• Is x + 1 = 2 absent from the array? ✓ Yes (cnt[2] = 0)
• Result: 1 is lonely ✓

For x = 3 (frequency = 2):

• Does 3 appear exactly once? ✗ No (frequency = 2)
• Result: 3 is not lonely (fails first condition)

For x = 5 (frequency = 1):

• Does 5 appear exactly once? ✓ Yes (frequency = 1)
• Is x - 1 = 4 absent from the array? ✓ Yes (cnt[4] = 0)
• Is x + 1 = 6 absent from the array? ✓ Yes (cnt[6] = 0)
• Result: 5 is lonely ✓

Final Answer: [1, 5]

Both 1 and 5 appear exactly once and have no adjacent numbers in the array, making them lonely numbers.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm involves:

1. Creating a Counter from the input list nums, which requires iterating through all n elements once - O(n)
2. Iterating through the Counter's items (at most n unique elements) to check conditions - O(n)
3. For each element x, checking cnt[x-1] and cnt[x+1] are both O(1) operations due to hash table lookups

Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The space is used for:

1. The Counter object cnt, which stores at most n key-value pairs (in the worst case where all elements are unique) - O(n)
2. The output list, which in the worst case could contain all n elements if they are all lonely numbers - O(n)

Therefore, the overall space complexity is O(n).

Here, n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using Standard Dictionary Instead of Counter

A common mistake is using a regular dictionary and checking for adjacent numbers with the in operator or get() method:

# Incorrect approach that may cause errors
frequency_map = {}
for num in nums:
    frequency_map[num] = frequency_map.get(num, 0) + 1

lonely_numbers = []
for number, frequency in frequency_map.items():
    if (frequency == 1 and 
        (number - 1) not in frequency_map and 
        (number + 1) not in frequency_map):
        lonely_numbers.append(number)

Why Counter is better: Counter automatically returns 0 for non-existent keys, making the code cleaner and avoiding potential KeyError exceptions. With Counter, frequency_map[number - 1] == 0 safely checks for absence, while with a regular dict you need explicit existence checks.

Pitfall 2: Modifying the Original Array During Iteration

Some might try to check conditions while iterating through the original array:

# Incorrect: This doesn't handle duplicates properly
lonely = []
for num in nums:
    if (nums.count(num) == 1 and 
        (num - 1) not in nums and 
        (num + 1) not in nums):
        lonely.append(num)
return lonely

Problems with this approach:

• Time complexity becomes O(n²) due to repeated count() and in operations
• Duplicate lonely numbers would be added to the result
• Inefficient for large arrays

Pitfall 3: Off-by-One Errors in Adjacent Number Checks

A subtle mistake is incorrectly checking adjacent numbers:

# Incorrect: Checking wrong adjacent values
if (frequency == 1 and 
    frequency_map[number - 1] == 1 and  # Wrong condition!
    frequency_map[number + 1] == 1):    # Wrong condition!

The correct logic: We want adjacent numbers to NOT exist (frequency == 0), not to exist exactly once.

Pitfall 4: Integer Overflow Concerns

While not typically an issue in Python, in other languages checking number + 1 or number - 1 for very large integers could cause overflow:

# Better practice for extreme edge cases
MAX_INT = 2**31 - 1
MIN_INT = -2**31

for number, frequency in frequency_map.items():
    if frequency == 1:
        # Check boundaries to avoid potential issues
        left_absent = (number == MIN_INT or frequency_map[number - 1] == 0)
        right_absent = (number == MAX_INT or frequency_map[number + 1] == 0)
        if left_absent and right_absent:
            lonely_numbers.append(number)

Solution: In Python, integers have arbitrary precision so overflow isn't a concern, but being aware of this issue is important when implementing in other languages like Java or C++.