Find All Lonely Numbers in the Array — Editorial

Opening the reading…

Intuitionthe definition separates frequency from adjacency

A lonely number has two independent requirements. First, it must occur exactly once, so duplicate values are rejected by their frequency. Second, neither neighboring value may occur anywhere in the array, so a singleton such as 6 is still not lonely if 5 or 7 appears.

A frequency map records both facts we need to test: how many times each value occurs and whether a value occurs at all. After building it, inspect each distinct value exactly once. Keep x only when its count is 1 and both x - 1 and x + 1 are absent. There is no need to search the original array repeatedly.

Approachtwo passes keep counting and checking separate

Create an unordered_map called freq and count every value in nums, because checking the original array for each candidate would repeat the same work many times.

Visit each key x in freq rather than every element of nums, because duplicates have the same frequency and neighbor information and only one check per distinct value is needed.

Reject x unless freq[x] equals 1, because a value appearing more than once fails the definition even when both of its neighbors are absent.

Check that freq.find(x - 1) is absent, because the lower adjacent value disqualifies x regardless of how many times it appears.

Check that freq.find(x + 1) is absent, because the upper adjacent value is equally disqualifying and both sides must be tested.

Append x to the result only when all three conditions pass, then return the result because the problem permits the lonely numbers in any order.

Complexityexpected bounds for hash-table operations

MEASURE	BOUND	WHY
Time	Expected O(n), worst-case O(n^2)	The first pass performs n frequency updates, and the second pass performs at most n key checks, each expected O(1). With ordinary hashing, no element is processed more than a constant number of times; in the worst collision pattern, hash operations can become linear.
Space	O(n) extra	The map stores one entry per distinct value, and there can be n distinct values. The returned vector is required output and is excluded from extra space. The bound is O(n) even when every input value is different.

Here n is the length of nums. The hash-table bounds are expected bounds; a deliberately bad collision pattern can degrade individual operations.

Annotated solutionC++ · two-pass hash map · direct translation of the definition

CPPBuild frequencies, then emit singleton keys with neither adjacent key present.

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findLonely(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            freq[x]++;
        }

        vector<int> result;
        for (auto& entry : freq) {
            int x = entry.first;
            int count = entry.second;

            if (count == 1 &&
                freq.find(x - 1) == freq.end() &&
                freq.find(x + 1) == freq.end()) {
                result.push_back(x);
            }
        }

        return result;
    }
};

The loop over freq is intentional: it visits each distinct number once, so the count stored in entry is already available. The two find calls test presence rather than frequency, which is exactly what the definition requires. A neighbor appearing once or ten times has the same effect: x is not lonely.

The sorting alternativewhen avoiding hashing matters more than linear expected time

You can sort nums and process each run of equal values. A run of length one handles the frequency condition, while the values immediately before and after the run reveal whether either neighbor exists. This is a genuine alternative when you prefer deterministic comparison-based work or want to avoid a hash table, but it modifies nums and costs O(n log n) time.

CPPSort the values, inspect each equal-value run, and test the surrounding values.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> findLonely(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> result;
        int n = static_cast<int>(nums.size());

        int i = 0;
        while (i < n) {
            int j = i + 1;
            while (j < n && nums[j] == nums[i]) {
                j++;
            }

            bool appearsOnce = (j - i == 1);
            bool noLowerNeighbor = (i == 0 || nums[i - 1] < nums[i] - 1);
            bool noUpperNeighbor = (j == n || nums[j] > nums[i] + 1);

            if (appearsOnce && noLowerNeighbor && noUpperNeighbor) {
                result.push_back(nums[i]);
            }

            i = j;
        }

        return result;
    }
};

The scan jumps from i to j after processing a complete run, so duplicate copies are never mistaken for separate candidates. The expression nums[i - 1] < nums[i] - 1 means the previous distinct value is at least two smaller; the analogous upper test means the next distinct value is at least two larger. This version uses O(1) auxiliary space besides the output, although sort may use implementation-dependent stack space.