Find Lucky Integer in an Array

Find Lucky Integer in an Array

What is this problem about?

The Find Lucky Integer in an Array coding problem defines a "lucky" integer as one whose frequency in the array is exactly equal to its value. For example, if the number 2 appears exactly twice, it is a lucky integer. You need to return the largest lucky integer in the array, or -1 if none exist.

Why is this asked in interviews?

This "Easy" difficulty question is common at Microsoft and Meta to test basic Hash Table interview patterns. It evaluates whether a candidate can correctly use a frequency map and then iterate through the map to apply a specific condition. It’s a foundational problem that tests clarity and efficiency in counting.

Algorithmic pattern used

This problem follows the Frequency Counting pattern.

1. Initialize a Hash Map or an array (if the range of values is small) to store the counts of each number.
2. Iterate through the input array once to populate the frequencies.
3. Iterate through the keys of the Hash Map.
4. If a key == map[key], then the key is a lucky integer.
5. Keep track of and return the maximum such key found.

Example explanation

Array: [2, 2, 3, 4, 3, 3]

1. Frequencies: {2: 2, 3: 3, 4: 1}.
2. Check 2: Freq is 2. Lucky! Current max = 2.
3. Check 3: Freq is 3. Lucky! Current max = 3.
4. Check 4: Freq is 1. Not lucky. Result: 3.

Common mistakes candidates make

• Sorting: Sorting the array to count elements, which is $O(n \log n)$ when a map can do it in $O(n)$.
• Incorrect return: Returning the frequency instead of the value (though they are equal, the logic should be clear).
• Tie-breaking: Returning the first lucky integer found instead of the largest.

Interview preparation tip

For all "frequency equals value" problems, use an array if the values are bounded (e.g., 1 to 500). Direct indexing is always faster than hashing in performance-critical code.