Scale Engineer

Find All Lonely Numbers in the Array

Med
#1959Time: 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).
Patterns
Counting
Data structures
ArrayHash Table

Prompt

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

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 counts to store number frequencies.
  • Iterate through each num in nums and populate the counts map.
  • Iterate through the keys of the counts map.
    • For a key num with value count, check if count is 1.
    • If it is, check if counts.containsKey(num - 1) is false AND counts.containsKey(num + 1) is false.
    • If both conditions are true, add num to the result list.
  • Return the result list.

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:

  1. Uniqueness: Check if its count in the map is 1.
  2. No Neighbors: Check if the map does not contain keys for num - 1 and num + 1. If a number num satisfies 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.

Solutions

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;  }}

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

← Previous

Previous problem

Next →

Next problem