Domain 1EasyCORE

Find Lucky Integer in an Array

The problem asks us to find a "lucky integer" in an array, which is defined as an integer whose frequency (number of occurrences) in the array matches its value. If there are multiple such integers, we should return the largest one. If no such integer exists, we return -1.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1394. Find Lucky Integer in an Array

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 63.1%


Problem Breakdown

The problem asks us to find a “lucky integer” in an array, which is defined as an integer whose frequency (number of occurrences) in the array matches its value. If there are multiple such integers, we should return the largest one. If no such integer exists, we return -1.

Inputs:

  • An array of integers arr where each integer is between 1 and 500 inclusive.
  • The length of the array is between 1 and 500 inclusive.

Outputs:

  • A single integer which is the largest lucky integer in the array, or -1 if no such integer exists.

Implicit Constraints/Edge Cases:

  • The array can contain duplicate values.
  • The array can have only one element.
  • All elements are positive integers within a specific range (1 to 500).

Intuition

The brute-force approach would involve iterating through each unique number in the array and counting its occurrences. If the count matches the number itself, we check if it’s the largest lucky integer found so far. This approach is inefficient with a time complexity of O(n^2) due to nested loops.

A better approach involves using a hash map (dictionary) to store the frequency of each number in one pass through the array. Then, we iterate through the dictionary to find the largest number whose frequency matches its value. This reduces the time complexity to O(n).

Approach

  1. Initialize a Dictionary: Create an empty dictionary to store the frequency of each integer in the array.
  2. Count Frequencies: Iterate through the array and populate the dictionary with the count of each integer.
  3. Find Largest Lucky Integer: Initialize a variable max_lucky to -1. Iterate through the dictionary items, checking if the key (integer) equals its value (frequency). If it does, update max_lucky if this integer is larger than the current max_lucky.
  4. Return Result: Return the value of max_lucky.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass to count frequencies and another pass through the dictionary.
  • Space Complexity: O(n) in the worst case, where all elements are unique.

Solution

def findLucky(arr):
    # Step 1: Initialize a dictionary to store the frequency of each integer
    freq = {}
    
    # Step 2: Count frequencies of each integer in the array
    for num in arr:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1
    
    # Step 3: Find the largest lucky integer
    max_lucky = -1
    for num, count in freq.items():
        if num == count and num > max_lucky:
            max_lucky = num
    
    # Step 4: Return the result
    return max_lucky

Edge Cases Handled

  • Single Element Array: The code correctly handles arrays with a single element by returning -1 if the element is not lucky, or the element itself if it is lucky.
  • All Elements Same: If all elements are the same and equal to their frequency, the largest one (which is also the only one) is returned.
  • No Lucky Integer: The code returns -1 if no integer in the array has a frequency matching its value.