Leetcode 1207: Unique Number of Occurrences
Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, and return false otherwise.
Problem
Approach
Steps
Complexity
Input: You are given an array arr of integers.
Example: Input: arr = [5,6,6,5,5,7]
Constraints:
• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000
Output: Return true if the number of occurrences of each value in the array is unique, otherwise return false.
Example: Output: true
Constraints:
Goal: The goal is to determine if all frequency counts in the array are unique.
Steps:
• Count the occurrences of each number in the array.
• Store the frequency of each number.
• Check if all frequency counts are unique.
Goal: The problem has constraints that ensure the input size is manageable and the array elements are bounded within a range.
Steps:
• 1 <= arr.length <= 1000
• -1000 <= arr[i] <= 1000
Assumptions:
• It is assumed that the input array is not empty, as the constraints guarantee at least one element.
• Input: Input: arr = [5,6,6,5,5,7]
• Explanation: The number 5 occurs 3 times, 6 occurs 2 times, and 7 occurs once. These frequencies are distinct.
• Input: Input: arr = [4,5]
• Explanation: Both 4 and 5 occur once, so the counts are not unique.
• Input: Input: arr = [0,1,2,0,1,2,2]
• Explanation: The number 0 occurs twice, 1 occurs twice, and 2 occurs three times. These frequencies are distinct.
Approach: The approach is to count the occurrences of each number in the array, store those counts, and then check if the counts are unique.
Observations:
• We need to count occurrences of each element in the array.
• A hash map can be used to store the frequencies of the elements.
• We will use a frequency counter, then check for duplicates among the counts.
Steps:
• Create a hash map to store the frequency of each element in the array.
• Store these frequencies in a separate list.
• Sort and check if there are any duplicate frequencies.
Empty Inputs:
• An empty array will not be valid according to the problem's constraints.
Large Inputs:
• Ensure that the solution works for large input arrays with up to 1000 elements.
Special Values:
• Handle cases where all elements have the same frequency.
Constraints:
• The array is guaranteed to have at least one element.
bool uniqueOccurrences(vector<int>& arr) {
int i = 0;
sort(arr.begin(),arr.end());
vector<int> ans;
while (i < arr.size()){
int count = 1;
for (int j = i+1; j< arr.size(); j++){
if (arr[i] == arr[j])
count++;
}
ans.push_back(count);
i = i + count;
}
sort(ans.begin(),ans.end());
for (int i = 0; i < ans.size() - 1; i++){
if (ans[i] == ans [i+1])
return false;
}
return true;
}
1 : Function Definition
bool uniqueOccurrences(vector<int>& arr) {
Define the function `uniqueOccurrences` which takes a vector `arr` and returns a boolean indicating whether all elements in `arr` have unique occurrences.
2 : Variable Initialization
int i = 0;
Initialize the variable `i` to 0, which will be used to iterate through the array.
3 : Sorting
sort(arr.begin(),arr.end());
Sort the array `arr` in non-decreasing order so that identical elements are adjacent to each other.
4 : Vector Initialization
vector<int> ans;
Initialize an empty vector `ans` to store the frequency counts of each unique element in the array.
5 : While Loop
while (i < arr.size()){
Start a while loop that will iterate through the array, processing each element.
6 : Frequency Count Initialization
int count = 1;
Initialize the variable `count` to 1, which will track the number of occurrences of the current element.
7 : Nested Loop for Frequency Count
for (int j = i+1; j< arr.size(); j++){
Start a nested for loop to count the occurrences of the current element starting from index `i`.
8 : Comparison of Adjacent Elements
if (arr[i] == arr[j])
Check if the element at index `i` is equal to the element at index `j`.
9 : Increment Count
count++;
If the elements are equal, increment the `count` to track the frequency of the element.
10 : Store Frequency Count
ans.push_back(count);
Push the current frequency count `count` into the vector `ans`.
11 : Update Index
i = i + count;
Update the value of `i` to skip over the elements that have been counted, moving to the next unique element.
12 : Sorting Frequencies
sort(ans.begin(),ans.end());
Sort the frequency counts in the vector `ans` to compare adjacent frequencies.
13 : Loop to Compare Frequencies
for (int i = 0; i < ans.size() - 1; i++){
Start a loop to compare adjacent elements in the sorted frequency vector `ans`.
14 : Check for Duplicates
if (ans[i] == ans [i+1])
Check if two adjacent frequency counts are equal, indicating that a frequency is not unique.
15 : Return False for Duplicates
return false;
If duplicate frequencies are found, return `false` to indicate that the occurrences are not unique.
16 : Return True
return true;
Return `true` if all frequencies are unique, meaning that no two elements in the array have the same occurrence count.
Best Case: O(n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The counting operation is O(n), and checking for duplicates among counts requires sorting, which takes O(n log n).
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required for the hash map and frequency list.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus