Find All Lonely Numbers in the Array
MedPrompt
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] <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
The most optimal approach uses a hash map to count the frequency of each number. This allows us to check the conditions for being lonely (uniqueness and absence of neighbors) in constant time on average for each number.
Algorithm
- Initialize an empty list
result. - Initialize a hash map
countsto store number frequencies. - Iterate through each
numinnumsand populate thecountsmap. - Iterate through the keys of the
countsmap.- For a key
numwith valuecount, check ifcountis 1. - If it is, check if
counts.containsKey(num - 1)is false ANDcounts.containsKey(num + 1)is false. - If both conditions are true, add
numto theresultlist.
- For a key
- Return the
resultlist.
Walkthrough
The solution involves two main passes over the data.
First Pass: We iterate through the input array nums and build a frequency map. A hash map is perfect for this, where keys are the numbers from the array and values are their counts. This pass takes O(N) time.
Second Pass: We iterate through the keys of the frequency map. For each number num:
- Uniqueness: Check if its count in the map is 1.
- No Neighbors: Check if the map does not contain keys for
num - 1andnum + 1. If a numbernumsatisfies all three conditions, it is added to the result list. This second pass takes O(U) time where U is the number of unique elements. The hash map lookups (get,containsKey) take O(1) time on average.
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map; class Solution { public List<Integer> findLonely(int[] nums) { Map<Integer, Integer> counts = new HashMap<>(); for (int num : nums) { counts.put(num, counts.getOrDefault(num, 0) + 1); } List<Integer> result = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : counts.entrySet()) { if (entry.getValue() == 1) { int num = entry.getKey(); if (!counts.containsKey(num - 1) && !counts.containsKey(num + 1)) { result.add(num); } } } return result; }}Complexity
Time
O(N), where N is the number of elements in `nums`. The first pass to build the map is O(N), and the second pass to check for lonely numbers is O(U), where U <= N. Total time is O(N).
Space
O(U), where U is the number of unique elements in `nums`. In the worst case, all elements are unique, so the space complexity is O(N).
Trade-offs
Pros
Optimal time complexity of O(N).
Conceptually clean and easy to reason about.
Cons
Requires extra space for the hash map, which can be up to O(N) in the worst case where all numbers are unique.
A more efficient approach involves sorting the array first. Sorting brings identical numbers together and places potential neighbors (x-1, x+1) next to x, making the checks much faster.
Algorithm
- Initialize an empty list
result. - Sort the input array
nums. - Handle edge cases for arrays of size 0 or 1.
- Check the first element
nums[0]: ifnums[1]is greater thannums[0] + 1, thennums[0]is lonely. - Iterate from the second element to the second-to-last element (
ifrom 1 ton-2):- For
nums[i], check ifnums[i-1] < nums[i] - 1andnums[i+1] > nums[i] + 1. If true,nums[i]is lonely.
- For
- Check the last element
nums[n-1]: ifnums[n-2]is less thannums[n-1] - 1, thennums[n-1]is lonely. - Return the
resultlist.
Walkthrough
First, we sort the input array nums. This costs O(N log N) time.
After sorting, we can iterate through the array in a single pass (O(N) time) to identify lonely numbers.
For each element nums[i], we need to check if it's unique and if its neighbors are absent. Because the array is sorted, we only need to check the immediate adjacent elements:
- Uniqueness:
nums[i]is unique ifnums[i-1] != nums[i]andnums[i+1] != nums[i]. - No Neighbors:
nums[i]-1is not present ifnums[i-1] != nums[i] - 1.nums[i]+1is not present ifnums[i+1] != nums[i] + 1. Combining these, a numbernums[i](for0 < i < n-1) is lonely ifnums[i-1] < nums[i] - 1andnums[i+1] > nums[i] + 1. Special care is taken for the first and last elements.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<Integer> findLonely(int[] nums) { List<Integer> result = new ArrayList<>(); if (nums.length == 0) { return result; } Arrays.sort(nums); if (nums.length == 1) { result.add(nums[0]); return result; } // Check first element if (nums[1] > nums[0] + 1) { result.add(nums[0]); } // Check middle elements for (int i = 1; i < nums.length - 1; i++) { if (nums[i-1] < nums[i] - 1 && nums[i+1] > nums[i] + 1) { result.add(nums[i]); } } // Check last element if (nums[nums.length - 2] < nums[nums.length - 1] - 1) { result.add(nums[nums.length - 1]); } return result; }}Complexity
Time
O(N log N), dominated by the sorting step. The subsequent linear scan is O(N).
Space
O(log N) or O(N), depending on the space used by the sorting algorithm's implementation (e.g., recursion stack for Quicksort, or temporary array for Mergesort).
Trade-offs
Pros
Significantly faster than the brute-force approach.
Passes the time limits for the given constraints.
Cons
Sorting modifies the input array, which might not be desirable. A copy can be made, but that uses O(N) space.
Not as time-efficient as the hash map approach.
This approach directly translates the problem definition into code. For each number in the array, we perform separate checks to see if it meets the three conditions for being a lonely number: appearing exactly once, and having no adjacent numbers (x-1, x+1) present in the array.
Algorithm
- Initialize an empty list
resultto store lonely numbers. - For each number
numin the input arraynums:- Initialize
count = 0andhasAdjacent = false. - Iterate through the array
numsagain with a second pointer (otherNum).- If
otherNum == num, incrementcount. - If
otherNum == num - 1orotherNum == num + 1, sethasAdjacenttotrue.
- If
- After the inner loop, if
count == 1andhasAdjacentisfalse, addnumto theresultlist.
- Initialize
- Return the
resultlist.
Walkthrough
We iterate through each element num of the input array nums.
For each num, we first check its frequency. We do this by iterating through the entire array again and counting how many times num appears. If the count is not equal to 1, we know it's not a lonely number and can move to the next element.
If the count is 1, we then proceed to check for the presence of its neighbors, num - 1 and num + 1. We perform another search through the array to see if either of these neighbors exists.
If neither num - 1 nor num + 1 is found in the array, and its count was 1, we've confirmed num is a lonely number and add it to our result list.
This process is repeated for all numbers in the input array.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> findLonely(int[] nums) { List<Integer> lonelyNumbers = new ArrayList<>(); for (int num : nums) { int count = 0; boolean hasAdjacent = false; // Check frequency and adjacent numbers in one pass for (int otherNum : nums) { if (otherNum == num) { count++; } else if (otherNum == num - 1 || otherNum == num + 1) { hasAdjacent = true; } } if (count == 1 && !hasAdjacent) { lonelyNumbers.add(num); } } return lonelyNumbers; }}Complexity
Time
O(N^2), where N is the number of elements in `nums`. The nested loops cause quadratic time complexity, as for each of the N elements, we iterate through the entire array again.
Space
O(K), where K is the number of lonely numbers. This is for the result list. Excluding the result list, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement directly from the problem statement.
Uses minimal extra space (O(1) besides the output list).
Cons
Highly inefficient due to the nested loop structure.
Will result in a "Time Limit Exceeded" (TLE) error for large inputs as specified in the constraints (N up to 10^5).
Solutions
Solution
class Solution {public List<Integer> findLonely(int[] nums) { Map<Integer, Integer> counter = new HashMap<>(); for (int num : nums) { counter.put(num, counter.getOrDefault(num, 0) + 1); } List<Integer> ans = new ArrayList<>(); counter.forEach((k, v)->{ if (v == 1 && !counter.containsKey(k - 1) && !counter.containsKey(k + 1)) { ans.add(k); } }); return ans; }}class Solution {public: vector<int> findLonely(vector<int> &nums) { unordered_map<int, int> counter; for (int num : nums) ++counter[num]; vector<int> ans; for (auto &e : counter) { int k = e.first, v = e.second; if (v == 1 && !counter.count(k - 1) && !counter.count(k + 1)) ans.push_back(k); } return ans; }};class Solution: def findLonely(self, nums: List[int]) -> List[int]: counter = Counter(nums) ans = [] for num, cnt in counter . items(): if cnt == 1 and counter[num - 1] == 0 and counter[num + 1] == 0: ans . append(num) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.