Find Lonely Numbers
Description
Given an integer array nums, find all the numbers x in nums that satisfy the following: x + 1 is not in nums, and x - 1 is not in nums.
If a valid number x appears multiple times, you only need to include it in the answer once. Return the result in any order.
Example 1:
Input: nums = [10, 6, 5, 8]
Output: [10, 8]
Explanation:
- 10: 10+1=11 not in nums, 10-1=9 not in nums. Lonely!
- 6: 6-1=5 is in nums. Not lonely.
- 5: 5+1=6 is in nums. Not lonely.
- 8: 8+1=9 not in nums, 8-1=7 not in nums. Lonely!
Example 2:
Input: nums = [1, 3, 5, 7]
Output: [1, 3, 5, 7]
Explanation: All numbers are lonely since no consecutive pairs exist.
Example 3:
Input: nums = [1, 2, 3]
Output: []
Explanation: No number is lonely - each has a neighbor (1 has 2, 2 has 1 and 3, 3 has 2).
Constraints
1 <= nums.length <= 10^5-10^6 <= nums[i] <= 10^6
Complexity
Show Complexity
- Time:
O(n) - Space:
O(n)
Hints
Show Hints
- Pattern
- Hash set for O(1) lookup
- Approach
- Create a set of all numbers. For each unique number x, check if (x-1) and (x+1) are absent from the set.
- Complexity
- Store all numbers in a set, then check each number
Solutions
Show PY Solution
from typing import List
def solution(nums: List[int]) -> List[int]:
s = set(nums)
result = []
for v in s:
if v - 1 not in s and v + 1 not in s:
result.append(v)
return result
# Step-by-step
# m = {}
# result = []
#
# for i in range(len(nums)):
# v = nums[i]
# if v in m:
# if v - 1 in m:
# m[v - 1] += 1
# m[v] += 1
# if v + 1 in m:
# m[v + 1] += 1
# m[v] += 1
# else:
# m[v] = 0
# if v - 1 in m:
# m[v - 1] += 1
# m[v] += 1
# if v + 1 in m:
# m[v + 1] += 1
# m[v] += 1
#
# result = []
# for k, v in m.items():
# if v == 0:
# result.append(k)
#
# return result