Find All Lonely Numbers in the Array

Medium
1149.

Find All Lonely Numbers in the Array

Find All Lonely Numbers in the Array is a medium coding problem on arrays, hash table and counting, asked in Amazon and Google interviews.

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^5
  • 0 <= nums[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findLonely = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 0 <= nums[i] <= 10^6

Hints for Find All Lonely Numbers in the Array

  1. Hint 1

    Two things must hold for x: it appears once, and both x - 1 and x + 1 are absent.

  2. Hint 2

    A frequency map answers both questions in constant time per value.

  3. Hint 3

    Alternatively sort the array: a unique x is lonely exactly when the value right before it is below x - 1 and the value right after it is above x + 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

  1. Sort a copy of nums ascending.
  2. For each position i with value x, reject it if the previous value is at least x - 1 (a duplicate or x - 1).
  3. Reject it too if the next value is at most x + 1 (a duplicate or x + 1).
  4. 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 res

Java

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