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 <= 1050 <= nums[i] <= 106Problem Overview: You are given an integer array and must return all lonely numbers. A number is lonely if it appears exactly once and neither num - 1 nor num + 1 exists in the array. The result can be returned in any order.
Approach 1: Frequency Map with Set Check (O(n) time, O(n) space)
This approach counts occurrences of each value using a hash map. First iterate through the array and build a frequency map. Then iterate through the keys and select numbers where frequency == 1 and both neighbors num - 1 and num + 1 are absent from the map. Hash lookups are constant time, so each check is efficient. This method works well for unsorted arrays and directly leverages structures commonly used in hash table and counting problems.
The key insight: a number is lonely only if it appears once and its adjacent values never appear in the dataset. A frequency map gives immediate access to both conditions. The algorithm performs a single pass to count values and another pass to evaluate loneliness.
Approach 2: Sorted Array Traversal (O(n log n) time, O(1) extra space)
Sort the array first, then scan it from left to right. Because the array is sorted, duplicate values and neighboring integers appear next to each other. For each element, check three conditions: it is different from the previous element, different from the next element, and neither adjacent value differs by exactly 1. If all conditions hold, the element is lonely. Sorting costs O(n log n), but the traversal afterward is a single linear pass.
This approach avoids extra memory and relies purely on ordering properties of a sorted array. It is useful when memory usage matters or when the input may already be sorted.
Recommended for interviews: The frequency map solution is typically expected because it achieves optimal O(n) time with clear logic. It shows you understand hashing for constant-time membership checks. The sorted traversal approach is still valuable because it demonstrates awareness of alternative tradeoffs between time and space.
This approach leverages a frequency map to count the occurrences of each number in the array. Then, we use a set to verify whether the adjacent numbers (x+1, x-1) are present. A number is confirmed as 'lonely' if it occurs only once in the array and its adjacent numbers do not exist in the array.
In Python, we use a Counter to track the frequencies. We iterate through each number and check if its count is one and its neighbors are absent in the set representation of the keys in the frequency dictionary. This confirms its loneliness.
Python
C++
Java
JavaScript
C#
Time Complexity: O(n), where n is the length of the array since we perform a constant-time check in a loop.
Space Complexity: O(n) for the frequency dictionary.
Sort the array and perform a linear traversal to identify lonely numbers. A sorted traversal allows easy checking of adjacent elements by considering surrounding elements directly.
We sort the array and then traverse it. For each number, check conditions based on adjacent numbers to ensure isolation, taking index edges as boundary conditions.
Python
C++
Java
JavaScript
C#
Time Complexity: O(n log n) due to sort operation.
Space Complexity: O(1) in-place, apart from return list, or O(n) considering result list storage linked to output size.
We use a hash table cnt to record the occurrence count of each number. Then, we iterate through the hash table. For each number and its occurrence count (x, v), if v = 1 and cnt[x - 1] = 0 and cnt[x + 1] = 0, then x is a lonely number, and we add it to the answer array.
After finishing the iteration, we return the answer array.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Frequency Map with Set Check | Time Complexity: O(n), where n is the length of the array since we perform a constant-time check in a loop. |
| Sorted Array Traversal | Time Complexity: O(n log n) due to sort operation. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map with Set Check | O(n) | O(n) | General case for unsorted arrays; fastest solution with constant-time lookups |
| Sorted Array Traversal | O(n log n) | O(1) extra space | When minimizing additional memory or when the array is already sorted |
Find All Lonely Numbers in the Array | Leetcode 2150 | Weekly Contest 277 Solution | Java • Pepcoding • 2,434 views views
Watch 9 more video solutions →Practice Find All Lonely Numbers in the Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor