# Find All Lonely Numbers in the Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-lonely-numbers-in-the-array)
Canonical: https://scaleengineer.com/dsa/problems/find-all-lonely-numbers-in-the-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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**.

**Example 1:**

**Input:** nums = [10,6,5,8]
**Output:** [10,8]
**Explanation:** 
- 10 is a lonely number since it appears exactly once and 9 and 11 does not appear in nums.
- 8 is a lonely number since it appears exactly once and 7 and 9 does not appear in nums.
- 5 is not a lonely number since 6 appears in nums and vice versa.
Hence, the lonely numbers in nums are [10, 8].
Note that [8, 10] may also be returned.

**Example 2:**

**Input:** nums = [1,3,5,3]
**Output:** [1,5]
**Explanation:** 
- 1 is a lonely number since it appears exactly once and 0 and 2 does not appear in nums.
- 5 is a lonely number since it appears exactly once and 4 and 6 does not appear in nums.
- 3 is not a lonely number since it appears twice.
Hence, the lonely numbers in nums are [1, 5].
Note that [5, 1] may also be returned.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 106`

# Approaches
## Brute Force
This approach directly translates the problem definition into code. For each number in the array, we perform separate checks to see if it meets the three conditions for being a lonely number: appearing exactly once, and having no adjacent numbers (`x-1`, `x+1`) present in the array.
**Time:** O(N^2), where N is the number of elements in `nums`. The nested loops cause quadratic time complexity, as for each of the N elements, we iterate through the entire array again. · **Space:** O(K), where K is the number of lonely numbers. This is for the result list. Excluding the result list, the space complexity is O(1).
**Pros:** Simple to understand and implement directly from the problem statement.; Uses minimal extra space (O(1) besides the output list).
**Cons:** Highly inefficient due to the nested loop structure.; Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints (N up to 10^5).
### Explanation
We iterate through each element `num` of the input array `nums`.
For each `num`, we first check its frequency. We do this by iterating through the entire array again and counting how many times `num` appears. If the count is not equal to 1, we know it's not a lonely number and can move to the next element.
If the count is 1, we then proceed to check for the presence of its neighbors, `num - 1` and `num + 1`. We perform another search through the array to see if either of these neighbors exists.
If neither `num - 1` nor `num + 1` is found in the array, and its count was 1, we've confirmed `num` is a lonely number and add it to our result list.
This process is repeated for all numbers in the input array.
```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findLonely(int[] nums) {
        List<Integer> lonelyNumbers = new ArrayList<>();
        for (int num : nums) {
            int count = 0;
            boolean hasAdjacent = false;
            
            // Check frequency and adjacent numbers in one pass
            for (int otherNum : nums) {
                if (otherNum == num) {
                    count++;
                } else if (otherNum == num - 1 || otherNum == num + 1) {
                    hasAdjacent = true;
                }
            }
            
            if (count == 1 && !hasAdjacent) {
                lonelyNumbers.add(num);
            }
        }
        return lonelyNumbers;
    }
}
```
### Algorithm
*   Initialize an empty list `result` to store lonely numbers.
*   For each number `num` in the input array `nums`:
    *   Initialize `count = 0` and `hasAdjacent = false`.
    *   Iterate through the array `nums` again with a second pointer (`otherNum`).
        *   If `otherNum == num`, increment `count`.
        *   If `otherNum == num - 1` or `otherNum == num + 1`, set `hasAdjacent` to `true`.
    *   After the inner loop, if `count == 1` and `hasAdjacent` is `false`, add `num` to the `result` list.
*   Return the `result` list.

## Sorting
A more efficient approach involves sorting the array first. Sorting brings identical numbers together and places potential neighbors (`x-1`, `x+1`) next to `x`, making the checks much faster.
**Time:** O(N log N), dominated by the sorting step. The subsequent linear scan is O(N). · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm's implementation (e.g., recursion stack for Quicksort, or temporary array for Mergesort).
**Pros:** Significantly faster than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** Sorting modifies the input array, which might not be desirable. A copy can be made, but that uses O(N) space.; Not as time-efficient as the hash map approach.
### Explanation
First, we sort the input array `nums`. This costs O(N log N) time.
After sorting, we can iterate through the array in a single pass (O(N) time) to identify lonely numbers.
For each element `nums[i]`, we need to check if it's unique and if its neighbors are absent. Because the array is sorted, we only need to check the immediate adjacent elements:
1.  **Uniqueness:** `nums[i]` is unique if `nums[i-1] != nums[i]` and `nums[i+1] != nums[i]`.
2.  **No Neighbors:** `nums[i]-1` is not present if `nums[i-1] != nums[i] - 1`. `nums[i]+1` is not present if `nums[i+1] != nums[i] + 1`.
Combining these, a number `nums[i]` (for `0 < i < n-1`) is lonely if `nums[i-1] < nums[i] - 1` and `nums[i+1] > nums[i] + 1`. Special care is taken for the first and last elements.
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findLonely(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums.length == 0) {
            return result;
        }
        
        Arrays.sort(nums);
        
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        
        // Check first element
        if (nums[1] > nums[0] + 1) {
            result.add(nums[0]);
        }
        
        // Check middle elements
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i-1] < nums[i] - 1 && nums[i+1] > nums[i] + 1) {
                result.add(nums[i]);
            }
        }
        
        // Check last element
        if (nums[nums.length - 2] < nums[nums.length - 1] - 1) {
            result.add(nums[nums.length - 1]);
        }
        
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list `result`.
*   Sort the input array `nums`.
*   Handle edge cases for arrays of size 0 or 1.
*   Check the first element `nums[0]`: if `nums[1]` is greater than `nums[0] + 1`, then `nums[0]` is lonely.
*   Iterate from the second element to the second-to-last element (`i` from 1 to `n-2`):
    *   For `nums[i]`, check if `nums[i-1] < nums[i] - 1` and `nums[i+1] > nums[i] + 1`. If true, `nums[i]` is lonely.
*   Check the last element `nums[n-1]`: if `nums[n-2]` is less than `nums[n-1] - 1`, then `nums[n-1]` is lonely.
*   Return the `result` list.

## Using a Hash Map (Frequency Counter)
The most optimal approach uses a hash map to count the frequency of each number. This allows us to check the conditions for being lonely (uniqueness and absence of neighbors) in constant time on average for each number.
**Time:** O(N), where N is the number of elements in `nums`. The first pass to build the map is O(N), and the second pass to check for lonely numbers is O(U), where U <= N. Total time is O(N). · **Space:** O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
**Pros:** Optimal time complexity of O(N).; Conceptually clean and easy to reason about.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst case where all numbers are unique.
### Explanation
The solution involves two main passes over the data.
**First Pass:** We iterate through the input array `nums` and build a frequency map. A hash map is perfect for this, where keys are the numbers from the array and values are their counts. This pass takes O(N) time.
**Second Pass:** We iterate through the keys of the frequency map. For each number `num`:
1.  **Uniqueness:** Check if its count in the map is 1.
2.  **No Neighbors:** Check if the map does *not* contain keys for `num - 1` and `num + 1`.
If a number `num` satisfies all three conditions, it is added to the result list. This second pass takes O(U) time where U is the number of unique elements. The hash map lookups (`get`, `containsKey`) take O(1) time on average.
```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findLonely(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }
        
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                int num = entry.getKey();
                if (!counts.containsKey(num - 1) && !counts.containsKey(num + 1)) {
                    result.add(num);
                }
            }
        }
        
        return result;
    }
}
```
### Algorithm
*   Initialize an empty list `result`.
*   Initialize a hash map `counts` to store number frequencies.
*   Iterate through each `num` in `nums` and populate the `counts` map.
*   Iterate through the keys of the `counts` map.
    *   For a key `num` with value `count`, check if `count` is 1.
    *   If it is, check if `counts.containsKey(num - 1)` is false AND `counts.containsKey(num + 1)` is false.
    *   If both conditions are true, add `num` to the `result` list.
*   Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> findLonely(int[] nums) {
    Map<Integer, Integer> counter = new HashMap<>();
    for (int num : nums) {
      counter.put(num, counter.getOrDefault(num, 0) + 1);
    }
    List<Integer> ans = new ArrayList<>();
    counter.forEach((k, v)->{
      if (v == 1 && !counter.containsKey(k - 1) &&
          !counter.containsKey(k + 1)) {
        ans.add(k);
      }
    });
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findLonely(vector<int> &nums) {
    unordered_map<int, int> counter;
    for (int num : nums)
      ++counter[num];
    vector<int> ans;
    for (auto &e : counter) {
      int k = e.first, v = e.second;
      if (v == 1 && !counter.count(k - 1) && !counter.count(k + 1))
        ans.push_back(k);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findLonely(self, nums: List[int]) -> List[int]: counter = Counter(nums) ans = [] for num, cnt in counter . items(): if cnt == 1 and counter[num - 1] == 0 and counter[num + 1] == 0: ans . append(num) return ans

```