Leetcode 2150: Find All Lonely Numbers in the Array
You are given an integer array ’nums’. A number ‘x’ is lonely if it appears exactly once and neither ‘x - 1’ nor ‘x + 1’ exist in the array. Return all lonely numbers in the array.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer array 'nums'.
Example: nums = [12, 6, 4, 8]
Constraints:
• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6
Output: Return all the lonely numbers in 'nums'. The result can be returned in any order.
Example: Output: [12, 8]
Constraints:
• The array should contain numbers that are lonely by the definition provided.
Goal: Identify numbers that appear only once and do not have adjacent numbers in the array.
Steps:
• Count the frequency of each number in the array.
• Check for each number if it appears exactly once and if its neighbors (x-1 and x+1) are not present in the array.
• Return the numbers that meet these conditions.
Goal: The array 'nums' will have valid integer values within the specified range, and its length will meet the constraint.
Steps:
• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^6
Assumptions:
• The input array may contain repeated numbers, but the goal is to identify the lonely numbers based on the conditions given.
• Input: Example 1: nums = [12, 6, 4, 8]
• Explanation: The lonely numbers are 12 and 8 because they appear exactly once, and their adjacent numbers (11, 13, 7, and 9) are not present in the array.
• Input: Example 2: nums = [2, 4, 6, 4]
• Explanation: The lonely numbers are 2 and 6. The number 4 is not lonely because it appears twice.
Approach: The approach involves counting the occurrences of each number and checking for adjacency conditions to identify lonely numbers.
Observations:
• To find lonely numbers, we need to consider both frequency and the presence of adjacent numbers.
• A frequency map is useful to determine which numbers appear exactly once. Additionally, checking for adjacent numbers is crucial.
Steps:
• Create a frequency map for all elements in 'nums'.
• For each element, check if its frequency is 1 and if its adjacent numbers (x-1 and x+1) are absent in the map.
• Store all elements that satisfy the lonely condition and return the result.
Empty Inputs:
• An empty input is not valid according to the constraints.
Large Inputs:
• The solution should handle large arrays up to the constraint of 10^5 elements efficiently.
Special Values:
• If there are no lonely numbers, the function should return an empty array.
Constraints:
• The input array contains valid integers within the given range.
vector<int> findLonely(vector<int>& nums) {
unordered_map<int, int> mp;
for(int num: nums) mp[num]++;
vector<int> res;
for(auto [x, cnt]: mp) {
if(cnt == 1 && !mp.count(x - 1) && !mp.count(x +1))
res.push_back(x);
}
return res;
}
1 : Function Declaration
vector<int> findLonely(vector<int>& nums) {
Function declaration to find all lonely numbers in the given array. Lonely numbers appear exactly once and do not have adjacent numbers.
2 : Variable Initialization
unordered_map<int, int> mp;
Create a hash map 'mp' to count the frequency of each number in the input 'nums' array.
3 : Counting Frequencies
for(int num: nums) mp[num]++;
Iterate through the 'nums' array and update the frequency count of each number in the 'mp' hash map.
4 : Variable Initialization
vector<int> res;
Initialize an empty vector 'res' to store the lonely numbers that will be found.
5 : Iteration
for(auto [x, cnt]: mp) {
Iterate through each key-value pair in the 'mp' hash map, where 'x' is the number and 'cnt' is its frequency.
6 : Condition Check
if(cnt == 1 && !mp.count(x - 1) && !mp.count(x +1))
Check if the current number 'x' appears exactly once ('cnt == 1') and does not have adjacent numbers ('x-1' and 'x+1') in the 'mp' map.
7 : Adding to Result
res.push_back(x);
If the number 'x' is lonely, add it to the 'res' vector.
8 : Return Statement
return res;
Return the 'res' vector containing all the lonely numbers found in the array.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) since we iterate over the array to build the frequency map and check each element's neighbors.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) for storing the frequency map of the array.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus