Find All Lonely Numbers in the Array

medium hash map counting

Problem

You are given an integer array nums. A number x is lonely when it appears exactly once in the array and neither x − 1 nor x + 1 is present anywhere in the array. Return all lonely numbers in any order.

Inputnums = [10, 6, 5, 8]

Output[10, 8]

10 appears once and has no 9 or 11, so it is lonely. 8 appears once and has no 7 or 9, so it is lonely. 5 and 6 are neighbors of each other, so neither is lonely.

nums (comma-separated)

def find_lonely(nums):
    count = {}
    for x in nums:
        count[x] = count.get(x, 0) + 1
    ans = []
    for x in nums:
        if count[x] == 1 and (x - 1) not in count and (x + 1) not in count:
            ans.append(x)
    return ans

function findLonely(nums) {
  const count = new Map();
  for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
  const ans = [];
  for (const x of nums) {
    if (count.get(x) === 1 && !count.has(x - 1) && !count.has(x + 1)) ans.push(x);
  }
  return ans;
}

class Solution {
    public int[] findLonely(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int x : nums) {
            if (count.get(x) == 1 && !count.containsKey(x - 1) && !count.containsKey(x + 1)) ans.add(x);
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}

vector<int> findLonely(vector<int>& nums) {
    unordered_map<int, int> count;
    for (int x : nums) count[x]++;
    vector<int> ans;
    for (int x : nums) {
        if (count[x] == 1 && !count.count(x - 1) && !count.count(x + 1)) ans.push_back(x);
    }
    return ans;
}

Explanation

A number is lonely only if two conditions hold at the same time: it is unique (appears exactly once), and it has no adjacent values (neither one less nor one more shows up anywhere in the array). Both checks are really questions about presence and frequency, which a hash map answers instantly.

First pass: build a frequency map count, where count[x] is how many times x appears. This single structure lets us answer "is value v in the array?" with a membership check and "how many times?" with a lookup.

Second pass: for every value x, we keep it as lonely when count[x] == 1 (unique) and both x − 1 and x + 1 are missing from the map. If any of those three checks fails, x has company and is skipped.

Example: nums = [10, 6, 5, 8]. For 10: count 1, and 9 and 11 are absent, so it is lonely. For 6: 5 is present, so it is not lonely. For 5: 6 is present, so it is not lonely. For 8: count 1, and 7 and 9 are absent, so it is lonely. Answer: [10, 8].

Two linear passes over the array, each map operation O(1) on average, so the whole thing runs in linear time.

Time: O(n) Space: O(n)