Find Lucky Integer In An Array - Leetcode Solution

Problem Statement:

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. 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, but 3 is the largest.

Example 3:

Input: arr = [2,2,2,3,3] Output: -1 Explanation: There are no lucky numbers in the array.

Solution:

The problem is simple and can be solved with a single pass over the array. We can use a dictionary to keep track of the frequency of each integer in the array. Then we can iterate over the dictionary and check if any integer in the dictionary has a frequency equal to its value. If such an integer exists, we can store the largest one in a variable and return it. Otherwise, we return -1.

Here is the detailed algorithm:

1. Initialize an empty dictionary to store the frequency of each integer in the array.
2. Iterate over the array and update the frequency of each integer in the dictionary.
3. Iterate over the keys in the dictionary and check if any key has a value equal to the key itself.
   • If such a key exists, check if it is greater than the current largest lucky integer.
     • If it is, set it as the new largest lucky integer.
4. Return the largest lucky integer found or -1 if no lucky integer exists.

Here is the Python code implementing the above algorithm:

def findLucky(arr: List[int]) -> int: freq = {} for num in arr: freq[num] = freq.get(num, 0) + 1

largest_lucky = -1
for num, count in freq.items():
    if num == count:
        if num > largest_lucky:
            largest_lucky = num
            
return largest_lucky

Time Complexity:

The time complexity of this algorithm is O(n), where n is the length of the input array. We make two passes over the array, but the size of the dictionary is bounded by the number of unique integers in the array, which is less than or equal to n.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the length of the input array. We store the frequency of each integer in a dictionary, which can have at most n unique keys.

1