Find All Lonely Numbers in the Array - Practice Coding Problems

Find All Lonely Numbers in the Array - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [10,6,5,8]

› Output: [10,8]

💡 Note: 10 appears once and neither 9 nor 11 exist. 8 appears once and neither 7 nor 9 exist. 6 and 5 have each other as neighbors.

Example 2 — With Duplicates

$ Input: nums = [1,3,5,3]

› Output: [1,5]

💡 Note: 1 appears once with no neighbors (0,2 missing). 5 appears once with no neighbors (4,6 missing). 3 appears twice so it's not lonely.

Example 3 — No Lonely Numbers

$ Input: nums = [1,2,3,4]

› Output: []

💡 Note: Each number has at least one adjacent neighbor: 1 has 2, 2 has 1&3, 3 has 2&4, 4 has 3.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [10,6,5,8] - check each number's loneliness

Lonely Check

Number x is lonely if: count(x)=1 AND x-1∉array AND x+1∉array

Result

Return all numbers meeting lonely criteria

Key Takeaway

🎯 Key Insight: A number is lonely only if it's unique AND isolated from its consecutive neighbors

Asked in

a Amazon 15 G Google 12 M Microsoft 8 f Facebook 6

The key insight is that a number is lonely if it appears exactly once AND neither of its adjacent values (x-1, x+1) exist in the array. The optimal approach uses a frequency map to count occurrences in O(n) time, then checks neighbor existence efficiently. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(n)	For each number, check if it appears once and its neighbors don't exist
Single Pass with Set	O(n)	O(n)	Build number set, then check lonely conditions in one optimized pass
Frequency Count with Hash Map	O(n)	O(n)	Use hash map to count frequencies, then check lonely conditions

Brute Force — Algorithm Steps

Get unique numbers from array
For each unique number, count occurrences
Check if x-1 and x+1 exist in array
Add to result if appears once and no neighbors

Visualization

Tap to expand

Step-by-Step Walkthrough

Get Unique Numbers

Extract all unique values from array

Check Each Number

Count occurrences and check for neighbors

Identify Lonely

Add numbers that appear once with no neighbors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums, int numsSize, int* returnSize) {
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int currentNum = nums[i];
        
        // Count occurrences of current number
        int count = 0;
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] == currentNum) {
                count++;
            }
        }
        
        if (count == 1) {
            // Check if neighbors exist
            int hasLeftNeighbor = 0, hasRightNeighbor = 0;
            for (int j = 0; j < numsSize; j++) {
                if (nums[j] == currentNum - 1) hasLeftNeighbor = 1;
                if (nums[j] == currentNum + 1) hasRightNeighbor = 1;
            }
            
            if (!hasLeftNeighbor && !hasRightNeighbor) {
                // Check if already added
                int alreadyAdded = 0;
                for (int k = 0; k < *returnSize; k++) {
                    if (result[k] == currentNum) {
                        alreadyAdded = 1;
                        break;
                    }
                }
                if (!alreadyAdded) {
                    result[*returnSize] = currentNum;
                    (*returnSize)++;
                }
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each unique number, we scan the entire array to count occurrences and check neighbors

⚠ Quadratic Growth

Space Complexity

O(n)

Set to store unique numbers and result array

⚡ Linearithmic Space

34.2K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler