This is our solution and implementation to problem #1207: Unique Number of Occurrences on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Unique Number of Occurrences on LeetCode.
Implementation Strategy
We will create a map countMap to count the number of occurences of each input. Then, we'll iterate over the input array, and for each item:
- if it's not in countMap, add it and set its value to 1.
- if it's in countMap, increment its value by 1.
Then, we'll create a new set counts with countMap.values to filter out duplicate occurences (i.e. if more than one input had the same number of occurences). If these two objects are the same size, return true. Otherwise, return false.
Space and Time Complexity
This has a time complexity of O(n) because we iterate over the input array once, countMap once (when creating the set), and because insertions into the map are of O(1) time. The space complexity is O(n) because we are storing up to n elements in countMap.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.