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] <= 106This 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.
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.
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.
| 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. |
Missing Number - Blind 75 - Leetcode 268 - Python • NeetCode • 139,225 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