Problem Link - Least Frequency
Problem Statement:
You are given an array of integers that may contain duplicate elements. Your task is to find the element that appears the least frequently in the array. If there are multiple elements with the same least frequency, return the smallest of these elements.
Approach:
To solve this problem efficiently, we count how often each number appears in the array using a hash map. Then, we look for the number with the smallest count. If multiple numbers have the same smallest count, we choose the smallest number among them. This way, we can quickly and accurately find the number that appears the least often and is the smallest if there’s a tie.
Here’s a step-by-step way to do this using a hash map:-
-
Count Frequencies: We create a map(frequencyMap) to count how many times each number appears in the array.
-
Find the Least Frequent Element: We look through our map to find the number that appears the least number of times. If there’s a tie (multiple numbers with the same frequency), we choose the smallest number.
-
Result: After checking, the number with the least frequency (and smallest in case of ties) is returned.
Time Complexity:
Counting frequencies takes O(n), and finding the least frequent element also takes O(n), resulting in an overall time complexity of O(n).
Space Complexity:
The space complexity is O(n) due to the unordered_map used to store the frequency of unique elements in the array.