{x}
blog image

Find All Lonely Numbers in the Array

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

Solution Explanation: Find All Lonely Numbers in the Array

This problem asks us to find all "lonely" numbers in an array. A number is considered lonely if it appears only once in the array and neither its neighbors (x-1 and x+1) are present in the array.

The most efficient approach uses a hash table (or dictionary) to count the occurrences of each number. This allows for quick lookups of both the count of a number and the presence of its neighbors.

Algorithm:

  1. Count Occurrences: Iterate through the input array nums and use a hash table (e.g., Counter in Python, HashMap in Java) to store the frequency of each number.

  2. Identify Lonely Numbers: Iterate through the hash table. For each number x and its count v:

    • If v is 1 (appears only once), and neither x-1 nor x+1 are present in the hash table (or their counts are 0), then x is a lonely number. Add it to the result list.

  3. Return Result: Return the list of lonely numbers.

Time Complexity: O(n), where n is the length of the input array. We iterate through the array once to count occurrences and then iterate through the hash table (whose size is at most n). Hash table lookups are considered O(1) on average.

Space Complexity: O(n) in the worst case, as the hash table may store all unique numbers from the input array.

Code Examples:

The code examples below demonstrate the solution in several programming languages. They all follow the same algorithmic steps outlined above.

Python:

from collections import Counter
 
def findLonely(nums):
    count = Counter(nums)
    lonely_numbers = []
    for num, freq in count.items():
        if freq == 1 and num - 1 not in count and num + 1 not in count:
            lonely_numbers.append(num)
    return lonely_numbers

Java:

import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
 
class Solution {
    public List<Integer> findLonely(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        List<Integer> lonelyNumbers = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            if (freq == 1 && !count.containsKey(num - 1) && !count.containsKey(num + 1)) {
                lonelyNumbers.add(num);
            }
        }
        return lonelyNumbers;
    }
}

C++:

#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
vector<int> findLonely(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int num : nums) {
        count[num]++;
    }
    vector<int> lonelyNumbers;
    for (auto const& [num, freq] : count) {
        if (freq == 1 && count.find(num - 1) == count.end() && count.find(num + 1) == count.end()) {
            lonelyNumbers.push_back(num);
        }
    }
    return lonelyNumbers;
}

JavaScript:

function findLonely(nums) {
    const count = {};
    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    const lonelyNumbers = [];
    for (const num in count) {
        const freq = count[num];
        if (freq === 1 && !(num - 1 in count) && !(parseInt(num) + 1 in count)) {
            lonelyNumbers.push(parseInt(num));
        }
    }
    return lonelyNumbers;
}

These examples illustrate the core logic. Adaptations for other languages would follow the same fundamental pattern of counting occurrences and then checking for loneliness based on frequency and neighbor presence.