Find All Lonely Numbers in the Array

MEDIUM

Description

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 <= 10⁵
0 <= nums[i] <= 10⁶

Approaches

Checkout 3 different approaches to solve Find All Lonely Numbers in the Array. Click on different approaches to view the approach and algorithm in detail.

Using a Hash Map (Frequency Counter)

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.

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 - 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 Analysis

Time Complexity: 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 Complexity: 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).

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Find All Lonely Numbers in the Array. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Find All Lonely Numbers in the Array

Patterns:

Counting

Data Structures:

ArrayHash Table