Watch 10 video solutions for Find Lucky Integer in an Array, a easy level problem involving Array, Hash Table, Counting. This walkthrough by Technosage has 4,399 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: arr = [2,2,3,4] Output: 2 Explanation: The only lucky number in the array is 2 because frequency[2] == 2.
Example 2:
Input: arr = [1,2,2,3,3,3] Output: 3 Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.
Example 3:
Input: arr = [2,2,2,3,3] Output: -1 Explanation: There are no lucky numbers in the array.
Constraints:
1 <= arr.length <= 5001 <= arr[i] <= 500Problem Overview: You are given an integer array arr. A number is called lucky if its value is equal to the number of times it appears in the array. Your task is to return the largest lucky integer. If no such number exists, return -1.
Approach 1: Using a Frequency Map (O(n) time, O(n) space)
Count how many times each number appears using a hash map. Iterate through the array once and update the frequency for each value. After building the map, iterate through the key-value pairs and check whether value == frequency. Track the maximum such value during the scan. Hash lookups and updates are constant time on average, making the overall complexity O(n). This approach works well for general cases and is the most common technique when solving frequency-based problems involving hash tables.
Approach 2: Using an Array to Track Frequencies (O(n) time, O(1) space)
The constraints limit values in arr to a small range, so you can replace the hash map with a counting array. Create a frequency array where the index represents the number and the value stores its count. Iterate through arr and increment the corresponding index. Then scan the frequency array and check which indices satisfy i == frequency[i], keeping the largest valid value. Since the array size is fixed by the constraint range, the extra space is effectively constant. This technique is a classic counting pattern frequently used in array problems.
Recommended for interviews: The frequency map approach is what most interviewers expect first. It demonstrates your ability to apply hash-based counting to reduce repeated scans. Mentioning the counting-array optimization shows deeper understanding of constraints and space tradeoffs, which signals stronger problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map (Hash Table) | O(n) | O(n) | General case when counting occurrences of elements in an array |
| Counting Array (Frequency Array) | O(n) | O(1) | When the value range is small and known in advance |