Watch 10 video solutions for Find All Lonely Numbers in the Array, a medium level problem involving Array, Hash Table, Counting. This walkthrough by Pepcoding has 2,434 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |