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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7
8

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 <= 10^5
  • 0 <= nums[i] <= 10^6

Solution

Method 1 – Hash Map Counting

Intuition

We count the frequency of each number in the array. A number is lonely if it appears exactly once and neither its immediate neighbors (x-1, x+1) appear in the array.

Approach

  1. Count the frequency of each number in nums using a hash map.
  2. For each unique number x:
    • If count[x] == 1 and count[x-1] == 0 and count[x+1] == 0, add x to the answer.
  3. Return the list of lonely numbers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    vector<int> findLonely(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (int x : nums) cnt[x]++;
        vector<int> ans;
        for (auto& [x, c] : cnt) {
            if (c == 1 && cnt[x-1] == 0 && cnt[x+1] == 0) ans.push_back(x);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func findLonely(nums []int) []int {
    cnt := map[int]int{}
    for _, x := range nums { cnt[x]++ }
    ans := []int{}
    for x, c := range cnt {
        if c == 1 && cnt[x-1] == 0 && cnt[x+1] == 0 {
            ans = append(ans, x)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public List<Integer> findLonely(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int x : cnt.keySet()) {
            if (cnt.get(x) == 1 && !cnt.containsKey(x-1) && !cnt.containsKey(x+1)) ans.add(x);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun findLonely(nums: IntArray): List<Int> {
        val cnt = mutableMapOf<Int, Int>()
        for (x in nums) cnt[x] = cnt.getOrDefault(x, 0) + 1
        val ans = mutableListOf<Int>()
        for ((x, c) in cnt) {
            if (c == 1 && cnt.getOrDefault(x-1, 0) == 0 && cnt.getOrDefault(x+1, 0) == 0) ans.add(x)
        }
        return ans
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def findLonely(self, nums: list[int]) -> list[int]:
        from collections import Counter
        cnt = Counter(nums)
        ans = []
        for x in cnt:
            if cnt[x] == 1 and cnt[x-1] == 0 and cnt[x+1] == 0:
                ans.append(x)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

use std::collections::HashMap;
impl Solution {
    pub fn find_lonely(nums: Vec<i32>) -> Vec<i32> {
        let mut cnt = HashMap::new();
        for &x in &nums { *cnt.entry(x).or_insert(0) += 1; }
        let mut ans = vec![];
        for (&x, &c) in &cnt {
            if c == 1 && !cnt.contains_key(&(x-1)) && !cnt.contains_key(&(x+1)) {
                ans.push(x);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    findLonely(nums: number[]): number[] {
        const cnt = new Map<number, number>();
        for (const x of nums) cnt.set(x, (cnt.get(x) ?? 0) + 1);
        const ans: number[] = [];
        for (const [x, c] of cnt) {
            if (c === 1 && !cnt.has(x-1) && !cnt.has(x+1)) ans.push(x);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We count and check each number once.
  • 🧺 Space complexity: O(n), for the hash map storing counts.