LeetCode Solutions Blog

Find Lucky Integer in an Array

Number: 1510

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given an array of integers, a "lucky integer" is an integer whose frequency in the array is equal to its value. The task is to return the largest lucky integer. If no lucky integer exists, return -1.

Key Insights

Use a hash table (or dictionary) to count the frequency of each integer.
Compare each integer with its frequency and check if they match.
Keep track of the maximum lucky integer found during the iteration.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(n), due to the usage of a hash table to store counts.

Solution

The solution involves iterating through the array and using a hash table to count how many times each number appears. After counting, iterate through the hash table to find all numbers where the number is equal to its count, which qualifies them as lucky integers. Finally, return the largest lucky integer, or -1 if none exist.

Code Solutions

# Define the function to find the lucky integer
def find_lucky(arr):
    # Create a dictionary to count the frequency of each number
    frequency = {}
    
    # Count the frequency of each element in the array
    for num in arr:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
    
    # Initialize the result with -1 (default if no lucky integer exists)
    lucky = -1
    
    # Iterate over each key in the dictionary
    for num, count in frequency.items():
        # If the number equals its frequency, check if it's the largest lucky integer so far
        if num == count:
            lucky = max(lucky, num)
    
    return lucky

# Example usage:
print(find_lucky([2,2,3,4]))  # Output: 2
print(find_lucky([1,2,2,3,3,3]))  # Output: 3
print(find_lucky([2,2,2,3,3]))  # Output: -1