Find Lucky Integer in an Array - Solution & Explanation
Problem Statement
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] <= 500
Approach Overview
Problem 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 1: Using a Frequency Map
This approach involves using a hash map (or dictionary) to store the frequency of each integer in the array. Once frequencies are calculated, iterate through the map to find integers whose value is equal to their frequency, and track the maximum of such values.
In this C solution, we use an array freq of size 501 to capture the frequency of numbers from 1 to 500. We then iterate over the original array updating our frequency array. Finally, we search for the maximum lucky number by checking if the frequency matches the number itself.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since the frequency array is of constant size (501).
Approach 2: Using an Array to Track Frequencies
This approach involves using an array to directly track the frequency of each integer. By using an array of fixed size, we can avoid using a hash map or dictionary, which optimizes space usage when the domain of the input elements is known.
Similar to our first C solution but highlighting direct array access instead of hash maps, this implementation calculates frequency using a fixed-size array from 1 to 500. The result is determined by comparing each index with its frequency count directly.
Complexity
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using a constant-size array.
Approach 3: Counting
We can use a hash table or an array cnt to count the occurrences of each number in arr. Then, we iterate through cnt to find the largest x such that cnt[x] = x. If there is no such x, return -1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the arr.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using a Frequency Map | Time Complexity: O(n), where n is the length of the array. |
| Using an Array to Track Frequencies | Time Complexity: O(n), where n is the length of the array. |
| Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
LeetCode 1394 | Find Lucky Integer in an Array | Day 20 | 100 Days_LeetCode_Challenge|DSAwithedSlash • edSlash • 8,110 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Lucky Integer in an Array easy or hard?
How to solve Find Lucky Integer in an Array in O(n)?
What is the best approach for Find Lucky Integer in an Array?
What data structure is used in Find Lucky Integer in an Array?
What is the time complexity of Find Lucky Integer in an Array?
Find Lucky Integer in an Array Python or Java solution approach
Is Find Lucky Integer in an Array asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Find Lucky Integer in an Array with our built-in code editor and test cases.
Practice on FleetCode