Problem Description
Given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value. Return the largest lucky integer in the array. If there is no lucky integer return -1.
Key Insights
- A lucky integer must satisfy the condition where its value is equal to its frequency in the array.
- We can utilize a hash table (or dictionary) to count the occurrences of each integer in the array.
- After counting, we can check which integers are lucky and keep track of the largest lucky integer found.
Space and Time Complexity
Time Complexity: O(n) - We traverse the array to count frequencies and then check the counts. Space Complexity: O(n) - The space used to store the frequency counts.
Solution
To solve the problem, we will use a hash table to count how many times each integer appears in the array. After populating this frequency count, we will iterate through the counts to find the largest integer that is equal to its count. If we find such an integer, we will return it; otherwise, we will return -1.