We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Lonely Numbers in the Array

Number: 2270

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer array nums, a number x is considered lonely if it appears exactly once in the array and neither x-1 nor x+1 appears in the array. Return all lonely numbers in nums (the order does not matter).

Key Insights

  • Use a hash map (or dictionary) to count the frequency of each number.
  • A number is lonely if its frequency is exactly 1 and its adjacent numbers (x-1 and x+1) are not present in the frequency map.
  • Iterating over the frequency map gives an O(n) solution which is efficient given the constraints.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array Space Complexity: O(n) for storing the frequency counts in the hash map

Solution

We first traverse the input array to build a frequency map that counts the occurrences of each number. Then, we iterate over the keys in the frequency map and check for each number if it appears exactly once and if its adjacent numbers (x-1 and x+1) do not exist in the map. If both conditions are true, we add the number to the result list. This method efficiently finds all lonely numbers using a hash table for constant time look-ups.

Code Solutions

def findLonely(nums):
    # Create a dictionary to count the frequency of each number
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1

    # List to store lonely numbers
    lonely_numbers = []
    # Iterate over each unique number and its frequency
    for num, count in frequency.items():
        # A number is lonely if it appears once and neither adjacent number exists
        if count == 1 and (num - 1 not in frequency) and (num + 1 not in frequency):
            lonely_numbers.append(num)
    return lonely_numbers

# Example usage:
print(findLonely([10, 6, 5, 8]))  # Expected output: [10, 8] (order may vary)
← Back to All Questions