Find Lucky Integer in an Array: Frequency Counting Made Simple

LeetCode 1394. Find Lucky Integer in an Array asks a fun question: given an array of integers, find the largest value that appears exactly as many times as its own value. If no such value exists, return -1.

For example, in [2, 2, 3, 4], the value 2 appears exactly 2 times. That makes 2 a "lucky" integer. The values 3 and 4 each appear only once, so they do not qualify. The answer is 2.

Why this problem matters

Find Lucky Integer is a gentle introduction to the frequency counting pattern. You build a hash map of value-to-count, then query it. This same technique powers dozens of harder problems like Top K Frequent Elements, Group Anagrams, and Valid Anagram. Mastering it here, on an easy problem, means you can focus on the harder logic when those problems layer on extra complexity.

The key insight

A "lucky" integer is one where value equals frequency. So the algorithm has two natural stages:

1. Count frequencies. Walk through the array and record how many times each value appears.
2. Find the largest match. Scan through the frequency map and collect every value where value == count. Return the largest one, or -1 if none exists.

That is the entire problem. No tricky edge cases, no nested data structures. Just count, then check.

The solution

from collections import Counter

def find_lucky(arr: list[int]) -> int:
    counts = Counter(arr)
    result = -1
    for num, freq in counts.items():
        if num == freq:
            result = max(result, num)
    return result

We start by building a frequency map with Counter. Then we iterate through every entry, checking whether the number equals its count. Whenever we find a match, we keep track of the largest one seen so far. If no match is ever found, result stays at -1.

You can also write this without Counter if you want to keep it explicit:

def find_lucky(arr: list[int]) -> int:
    counts = {}
    for num in arr:
        counts[num] = counts.get(num, 0) + 1
    result = -1
    for num, freq in counts.items():
        if num == freq:
            result = max(result, num)
    return result

Both versions run in O(n) time and O(n) space. The Counter version is more concise, but the manual version is better for showing your thought process in an interview.

Visual walkthrough

The walkthrough shows every stage of the algorithm on [2, 2, 3, 4]. First we count, then we compare each value to its frequency, then we pick the largest match. The entire process takes two passes through the data.

Complexity analysis

Time: The frequency map approach makes one pass to count and one pass to check. Both are O(n), so the total is O(n). Sorting would work too, but O(n log n) is slower than necessary.

Space: The hash map stores at most n entries (one per distinct value). This is O(n) extra memory. The sorting approach avoids extra space but sacrifices time.

The building blocks

1. Frequency counter

The act of walking through a collection and counting how often each element appears. You initialize an empty map, and for each element you increment its count. This is the single most common hash map pattern in interview problems.

counts = {}
for item in collection:
    counts[item] = counts.get(item, 0) + 1

2. Map scan with a condition

After building the frequency map, you iterate through its entries and apply a filter. Here the condition is value == count, but the same pattern works for "find all elements with count greater than n/2" (majority element), "find elements that appear exactly once" (single number), and many others.

for key, value in map.items():
    if some_condition(key, value):
        process(key)

3. Tracking a running maximum

As you scan through candidates, you maintain the best answer seen so far. Initialize to -1 (or negative infinity), and update whenever you find something better. This micro-pattern shows up in nearly every problem that asks you to "return the largest" or "return the best."

best = -1
for candidate in candidates:
    if is_valid(candidate):
        best = max(best, candidate)

Edge cases

• No lucky integer exists. For [5], the frequency map is {5: 1}. Since 5 != 1, return -1.
• Multiple lucky integers. For [1, 2, 2, 3, 3, 3], both 2 (appears twice) and 3 (appears three times) are lucky. Return 3 because it is the largest.
• Value 1 appearing once. The array [1, 2, 3] contains 1 appearing exactly once. Since 1 == 1, the value 1 is lucky.
• All elements are the same. For [3, 3, 3], the map is {3: 3}. Since 3 == 3, return 3.
• Large values with low frequency. A value like 100 would need to appear exactly 100 times to be lucky. If it only appears twice, it does not qualify.

From understanding to recall

This problem is simple enough to solve on first reading. The real challenge is recognizing the frequency counting pattern instantly when it appears inside a harder problem. Two weeks from now, when you see a question that requires counting occurrences and then querying by count, you want the pattern to fire automatically.

That is what spaced repetition drills. CodeBricks breaks Find Lucky Integer into its individual building blocks, the frequency counter and the map scan, and has you type them from scratch at increasing intervals. After a few review cycles, the code lives in your fingers. You do not need to re-derive it from first principles every time.

Related posts

• Contains Duplicate - The simplest hash set problem, using a set to detect repeated values in a single pass
• Top K Frequent Elements - Takes the frequency counting pattern further by finding the k most common elements using bucket sort
• Happy Number - Another easy problem that uses a hash set for cycle detection, building on the same "have I seen this before?" idea

The frequency counting pattern is one of the most reusable tools in your interview toolkit. Learn it here on an easy problem, and you will recognize it everywhere.