Find All Lonely Numbers In The Array - Leetcode Solution

Problem Statement:

A lonely number is an element in an array that appears exactly once. Given an integer array arr, return an array of all the lonely numbers in arr. You can return the answer in any order.

Example 1:

Input: arr = [1,2,3,3,4,5] Output: [1,2,4,5] Explanation: 2, 4, and 5 are the lonely numbers.

Example 2:

Input: arr = [1,1,2,2] Output: []

Explanation: There are no lonely numbers in arr.

Solution:

To find the lonely numbers in the array, we need to traverse the array and count the occurrences of each number. If the count of any number is 1, then that number is a lonely number.

For this, we can use a hash table to store the count of each number in the array. We can then iterate through the hash table and find the lonely numbers.

Here is the complete solution in Python:

class Solution:
    def findLonely(self, arr: List[int]) -> List[int]:
        # create an empty hash table
        count = {}

        # traverse the array and count the occurrences of each number
        for n in arr:
            if n in count:
                count[n] += 1
            else:
                count[n] = 1

        # find the lonely numbers from the hash table
        lonely = []
        for n, c in count.items():
            if c == 1:
                lonely.append(n)

        return lonely

Time Complexity:

The time complexity of the above solution is O(n), where n is the length of the input array. This is because we traverse the array only once to count the occurrences of each number.

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the input array. This is because we use a hash table to store the count of each number in the array. The size of the hash table can be at most n, if all the elements in the array are unique.

1