2150. Find All Lonely Numbers in the Array

MediumArrayHash TableCounting
Leetcode Link

Problem Description

In this problem, you are given an integer array called nums. A number x is considered lonely if it meets two conditions:

  1. It appears only once in the array (nums).
  2. Neither x + 1 (the next consecutive number) nor x - 1 (the previous consecutive number) appear in the array.

Your objective is to find all the lonely numbers within the nums array and return them. The order in which you return these lonely numbers does not matter, meaning they can be in any sequence.

Intuition

The intuition behind the solution to this problem is to determine the occurrence of each number as well as the occurrence of its immediate neighbors (i.e., num - 1 and num + 1). To efficiently manage this, a Counter from Python's collections module is useful because it enables us to count the occurrences of each number in nums with ease.

Once we have the counts of each number, we can iterate through the items in the counter, which consist of the number and its count. During the iteration, we apply the conditions that define loneliness:

  • The count of the number num should be exactly 1 (it appears only once).
  • The count of num - 1 should be 0 (no adjacent smaller number).
  • The count of num + 1 should be 0 (no adjacent larger number).

If a number satisfies all three conditions, it is a lonely number and is added to the result list (ans). After the iteration is complete, the list ans is returned as the list of all lonely numbers found in the array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

The solution uses a hash table, specifically the Counter class from Python's collections module, to keep track of the frequency with which each number appears in the nums array. This is a common pattern when dealing with problems that require you to track the occurrences of elements because Counter provides an efficient way to store and query frequencies.

Here's a step-by-step explanation of the implementation:

  1. Initialize the Counter with the nums array. The Counter will create a hash table where the keys are the numbers from the array and the values are the counts of each number.

    1counter = Counter(nums)

  2. Create an empty list ans that will eventually contain all the lonely numbers.

    1ans = []

  3. Iterate over the items in the counter. For each iteration, you have a num which is the number from the array and cnt which is the count of how many times that number appears.

    1for num, cnt in counter.items():

  4. Inside the loop, you apply three checks for each number based on the definition of a lonely number:

    • Check if the current number num appears only once (cnt == 1).
    • Check if the number immediately smaller than the current number (num - 1) does not appear in the array (counter[num - 1] == 0).
    • Check if the number immediately larger than the current number (num + 1) does not appear in the array (counter[num + 1] == 0).

  5. If all three checks pass, it means that num is a lonely number, and you append it to the ans list.

    1if cnt == 1 and counter[num - 1] == 0 and counter[num + 1] == 0:
2    ans.append(num)

  6. After the loop finishes, the ans list contains all the lonely numbers and the function returns this list.

    1return ans

By using Counter, we achieve a solution that is simple and efficient with respect to time complexity since we look up the counts in constant time O(1) and we only iterate through the elements of the array once, making the overall time complexity O(N), where N is the number of elements in nums.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth first search?

Example Walkthrough

Let's consider an example to illustrate the solution approach. Suppose we have the following nums array:

1nums = [4, 10, 5, 8, 20, 15, 11, 10]

Follow these steps to find all the lonely numbers:

  1. Initialize the Counter with the nums array:

    1counter = Counter([4, 10, 5, 8, 20, 15, 11, 10])
2# counter now looks like: {4:1, 10:2, 5:1, 8:1, 20:1, 15:1, 11:1}

  2. Create an empty list ans to hold the lonely numbers:

    1ans = []

  3. Iterate over the items in the counter:

    1for num, cnt in counter.items():
2    # First iteration: num = 4, cnt = 1
3    # Second iteration: num = 10, cnt = 2
4    # and so on...

  4. Apply the checks for loneliness:

    • In the first iteration, num is 4 and cnt is 1.

      • Check if 4 appears only once: Yes (cnt == 1).
      • Check if 3 appears in the array: No (counter[3] == 0).
      • Check if 5 appears in the array: Yes (counter[5] != 0), so 4 is not lonely since its immediate larger neighbor exists.

    • Skipping to the next number meeting first condition which is 5.

      • Check if 5 appears only once: Yes (cnt == 1).
      • Check if 4 appears in the array: Yes (counter[4] != 0), so 5 is not lonely since its immediate smaller neighbor exists.

    • Skipping ahead to numbers that meet the first condition (20 and 15).

      • For num = 20, it appears only once, and neither 19 nor 21 appear in the array. So, 20 is lonely.
      • For num = 15, it appears only once, and neither 14 nor 16 appear in the array. So, 15 is lonely.

    • Continue this process for the rest of the numbers.

  5. After applying the loneliness checks and iterating through all the counter's items, find that 20 and 15 meet the criteria for being lonely numbers:

    1ans.append(20)
2ans.append(15)

  6. Finally, return the ans list, which contains all the lonely numbers found in nums:

    1return ans
2# The final returned ans list is: [20, 15]

The final output for our example is [20, 15], which means 20 and 15 are the lonely numbers in the given nums array. They appear only once, and neither their immediate smaller nor larger neighbors appear in the array.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def findLonely(self, nums: List[int]) -> List[int]:
6        # Create a counter for all numbers in the list
7        num_counter = Counter(nums)
8        # Initialize an empty list to store lonely numbers
9        lonely_numbers = []
10      
11        # Iterate through the items in the counter
12        for num, count in num_counter.items():
13            # Check if the number appears only once and neither (num-1) nor (num+1) appear
14            if count == 1 and num_counter[num - 1] == 0 and num_counter[num + 1] == 0:
15                # If conditions are met, append the number to the lonely_numbers list
16                lonely_numbers.append(num)
17              
18        # Return the list of lonely numbers
19        return lonely_numbers
20
1import java.util.Map;
2import java.util.HashMap;
3import java.util.List;
4import java.util.ArrayList;
5
6class Solution {
7    // This method finds all elements in the array that stand alone without
8    // any adjacent or duplicate elements
9    public List<Integer> findLonely(int[] nums) {
10        // Create a HashMap to store the frequency of each number in the array
11        Map<Integer, Integer> frequencyMap = new HashMap<>();
12      
13        // Iterate through the array and populate the frequency map
14        for (int num : nums) {
15            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
16        }
17      
18        // Initialize a list to store the lonely numbers
19        List<Integer> lonelyNumbers = new ArrayList<>();
20      
21        // Iterate through the map to find lonely numbers
22        frequencyMap.forEach((number, count) -> {
23            // A number is lonely if it appears exactly once and neither of its
24            // adjacent numbers (number - 1, number + 1) are present in the array.
25            if (count == 1 && !frequencyMap.containsKey(number - 1)
26                && !frequencyMap.containsKey(number + 1)) {
27                lonelyNumbers.add(number);
28            }
29        });
30      
31        // Return the list of lonely numbers
32        return lonelyNumbers;
33    }
34}
35
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    // Function to find 'lonely' integers in the array.
8    // An integer is 'lonely' if its count is one and no adjacent integers (num - 1, num + 1) are present.
9    vector<int> findLonely(vector<int>& nums) {
10        // Create a hash map to keep track of the frequency of each number in the array.
11        unordered_map<int, int> frequencyMap;
12      
13        // Iterate over the array and increment the count for each number in the frequencyMap.
14        for (int num : nums) {
15            ++frequencyMap[num];
16        }
17      
18        // Prepare the answer vector to store the 'lonely' numbers.
19        vector<int> lonelyNumbers;
20      
21        // Iterate through the elements of frequencyMap
22        for (const auto& element : frequencyMap) {
23            int number = element.first;        // The number itself
24            int count = element.second;        // Frequency of the number
25          
26            // Check if the count is 1 (unique number) and both adjacent numbers do not exist.
27            if (count == 1 && !frequencyMap.count(number - 1) && !frequencyMap.count(number + 1)) {
28                // If conditions are satisfied, add number to the 'lonely' numbers list.
29                lonelyNumbers.push_back(number);
30            }
31        }
32      
33        // Return the list of 'lonely' numbers.
34        return lonelyNumbers;
35    }
36};
37
1function findLonely(nums: number[]): number[] {
2    // Initialize a hashMap to store the frequency of each number in the array
3    let frequencyMap: Map<number, number> = new Map();
4
5    // Populate the frequency map with counts of each number
6    for (let num of nums) {
7        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
8    }
9
10    // Initialize an array to store lonely numbers
11    let lonelyNumbers: Array<number> = [];
12
13    // Iterate through the entries of the frequency map
14    for (let [num, count] of frequencyMap.entries()) {
15        // Check if the current number is lonely, i.e., count is 1 and neither num-1 nor num+1 exist in the map
16        // If conditions are met, add the number to the lonelyNumbers array
17        if (count === 1 && !frequencyMap.has(num - 1) && !frequencyMap.has(num + 1)) {
18            lonelyNumbers.push(num);
19        }
20    }
21
22    // Return the array containing all lonely numbers
23    return lonelyNumbers;
24}
25
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The time complexity of the code is primarily determined by three factors: the creation of the counter which counts the occurrences of each element, the iteration through the counter dictionary, and the checks performed for each number.

  1. Creating the counter from the nums list takes O(n) time where n is the number of elements in the nums list because it requires one pass through all elements.

  2. Iterating through the counter dictionary's items also takes O(n) in the worst case, which is when all elements in nums are unique. We need to clarify this is "worst case" because the counter may have fewer than n keys if there are duplicate values in nums.

  3. For each element in the counter, we check if the cnt is 1 and if the adjacent numbers num - 1 and num + 1 are not present. These checks are constant-time operations, O(1), because dictionary lookup is an O(1) operation on average due to hash table implementation.

Combining these factors, the overall time complexity is O(n) + O(n) * O(1), which simplifies to O(n).

Space Complexity

The space complexity involves the space taken up by the counter dictionary and the ans list.

  1. The counter dictionary will hold at most n key-value pairs if all elements in nums are unique, resulting in a space complexity of O(n).

  2. The ans list can also hold at most n elements in the worst case, where every element is lonely. Therefore, the space complexity for the ans list is also O(n).

Therefore, the combined space complexity of the algorithm is also O(n), where n is the number of elements in the nums list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫