Find All Lonely Numbers in the Array

Problem Description

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. Return all lonely numbers in nums. You may return the answer in any order.

Key Insights

• A number is considered lonely if it appears exactly once in the array.
• Adjacent numbers (one less and one more than the lonely number) must not be present in the array.
• We can utilize a hash table to count occurrences of each number and track their presence efficiently.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input array nums, as we traverse the array to count occurrences and check for adjacent numbers.
Space Complexity: O(n) - for storing the counts and presence of the numbers in a hash table.

Solution

To solve the problem, we can follow these steps:

1. Use a hash table (or dictionary) to count the occurrences of each number in the array.
2. Create a set to keep track of numbers that are present in the array for quick lookup.
3. Iterate through the keys of the count hash table:
   • Check if the number appears exactly once.
   • Ensure that neither x + 1 nor x - 1 is present in the set of numbers.
4. If both conditions are satisfied, add the number to the result list.

This approach effectively combines counting and presence checking to identify lonely numbers.

Code Solutions