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] <= 500This 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.
C++
Java
Python
C#
JavaScript
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).
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), using a constant-size array.
| 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. |
Find Lucky Integer in an Array | Leetcode 1394 • Technosage • 3,018 views views
Watch 9 more video solutions →Practice Find Lucky Integer in an Array with our built-in code editor and test cases.
Practice on FleetCode