Find All Lonely Numbers in the Array — Problem & Solution
Find All Lonely Numbers in the Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find All Lonely Numbers in the Array is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A value x in the integer array nums is lonely when it occurs exactly once in nums and neither x - 1 nor x + 1 occurs anywhere in nums.
Return every lonely value in ascending order. If no value is lonely, return an empty array.
Example 1
Input: nums = [12,7,6,9]
Output: [9,12]
Explanation: `12` has no `11` or `13` beside it and `9` has no `8` or `10`. `6` and `7` are neighbours of each other, so neither is lonely.
Example 2
Input: nums = [2,4,4,7,3]
Output: [7]
Explanation: `4` repeats, and `2` and `3` each have a neighbour value present.
Example 3
Input: nums = [5,5]
Output: []
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^6
Hints for Find All Lonely Numbers in the Array
Hint 1
Two things must hold for
x: it appears once, and bothx - 1andx + 1are absent.Hint 2
A frequency map answers both questions in constant time per value.
Hint 3
Alternatively sort the array: a unique
xis lonely exactly when the value right before it is belowx - 1and the value right after it is abovex + 1.
How to solve Find All Lonely Numbers in the Array
After sorting, everything that could disqualify x — another copy of x, or the values x - 1 and x + 1 — would sit immediately next to it. So one pass over the sorted array with a look at each element's two neighbours decides loneliness.
Approach
- Sort a copy of
numsascending. - For each position
iwith valuex, reject it if the previous value is at leastx - 1(a duplicate orx - 1). - Reject it too if the next value is at most
x + 1(a duplicate orx + 1). - Every value that survives both checks is lonely; they are collected in ascending order already.
Why it works
In a sorted array the element before x is the largest value not after it. If x repeats, that neighbour equals x; if x - 1 is present (and x is unique), that neighbour is exactly x - 1; otherwise it is smaller than x - 1. The same argument mirrored covers the element after x, so the two comparisons are equivalent to the definition.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- A value that appears twice is never lonely, even if its neighbours are missing.
- The output order is fixed (ascending) — a hash-map solution must sort its result.
- The first and last sorted elements have only one neighbour to check.
Reference solution
Python
from typing import List
def findLonely(nums: List[int]) -> List[int]:
a = sorted(nums)
n = len(a)
res = []
for i in range(n):
x = a[i]
if i > 0 and a[i - 1] >= x - 1:
continue
if i + 1 < n and a[i + 1] <= x + 1:
continue
res.append(x)
return resJava
public static int[] findLonely(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = a[i];
if (i > 0 && a[i - 1] >= x - 1) continue;
if (i + 1 < n && a[i + 1] <= x + 1) continue;
res.add(x);
}
int[] out = new int[res.size()];
for (int i = 0; i < out.length; i++) out[i] = res.get(i);
return out;
}C++
vector<int> findLonely(vector<int>& nums) {
vector<int> a(nums.begin(), nums.end());
sort(a.begin(), a.end());
int n = a.size();
vector<int> res;
for (int i = 0; i < n; i++) {
int x = a[i];
if (i > 0 && a[i - 1] >= x - 1) continue;
if (i + 1 < n && a[i + 1] <= x + 1) continue;
res.push_back(x);
}
return res;
}JavaScript
var findLonely = function(nums) {
var a = nums.slice().sort(function(p, q) { return p - q; });
var res = [];
for (var i = 0; i < a.length; i++) {
var x = a[i];
if (i > 0 && a[i - 1] >= x - 1) continue;
if (i + 1 < a.length && a[i + 1] <= x + 1) continue;
res.push(x);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets