Skip to main content
Talentd

Find All Lonely Numbers in the Array - Solution & Explanation

MediumArrayHash TableCounting12 min readAsked at: Apple, Google
Practice this problem

Problem Statement

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 <= 105
  • 0 <= nums[i] <= 106

Approach Overview

Problem 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 1: Frequency Map with Set Check

This 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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

Approach 2: Sorted Array Traversal

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

Approach 3: Hash Table

We use a hash table cnt to record the occurrence count of each number. Then, we iterate through the hash table. For each number and its occurrence count (x, v), if v = 1 and cnt[x - 1] = 0 and cnt[x + 1] = 0, then x is a lonely number, and we add it to the answer array.

After finishing the iteration, we return the answer array.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for the frequency dictionary.

Sorted Array Traversal

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.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Map with Set CheckO(n)O(n)General case for unsorted arrays; fastest solution with constant-time lookups
Sorted Array TraversalO(n log n)O(1) extra spaceWhen minimizing additional memory or when the array is already sorted

Video Solution

Find All Lonely Numbers in the Array | Leetcode 2150 | Weekly Contest 277 Solution | Java • Pepcoding • 2,462 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find All Lonely Numbers in the Array easy or hard?
The problem is classified as Medium because it requires recognizing two conditions simultaneously: uniqueness and absence of adjacent values. Once you identify that a hash map can track frequencies and neighbor presence, the implementation becomes straightforward.
How to solve Find All Lonely Numbers in the Array in O(n)?
Use a hash map to count frequencies of every number in the array. Then iterate through the keys and select numbers where frequency equals 1 and neither num-1 nor num+1 exists in the map. Hash lookups are O(1), so the entire algorithm completes in linear time.
Find All Lonely Numbers in the Array Python or Java solution
In Python, use a dictionary or collections.Counter to track frequencies, then filter numbers whose count is 1 and whose neighbors are absent. In Java, use a HashMap<Integer, Integer> for counts and perform the same checks. Both implementations run in O(n) time and O(n) space.
What is the best approach for Find All Lonely Numbers in the Array?
The optimal approach uses a hash map (frequency map). Count how many times each number appears, then check whether the number appears exactly once and whether its neighbors (num-1 and num+1) are missing. This runs in O(n) time with O(n) space and works efficiently for unsorted arrays.
What data structure is used in Find All Lonely Numbers in the Array?
The primary data structure is a hash map (or dictionary) used to store frequency counts. This enables constant-time lookups for num, num-1, and num+1 checks. Arrays and sorting can also be used as an alternative approach.
What is the time complexity of Find All Lonely Numbers in the Array?
The optimal hash map solution runs in O(n) time because each element is processed a constant number of times. Building the frequency map takes O(n) and verifying loneliness for each unique number also takes O(n). Space complexity is O(n) for storing counts.
Is Find All Lonely Numbers in the Array asked at Google, Amazon, or Meta?
Problems involving frequency maps and neighbor checks are common in interviews at companies like Amazon and Meta. Variations appear in array and hash table interview rounds where candidates must efficiently detect unique elements with adjacency constraints.

Ready to solve this problem?

Practice Find All Lonely Numbers in the Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Frequency of the Most Frequent Element