#1394

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Lucky Integer in an Array

Identify the largest lucky integer in an array by counting frequencies and comparing values with their occurrences efficiently.

array hash table counting

Problem Statement

Given an array of integers arr, define a lucky integer as one whose value is equal to its frequency in the array. Your task is to determine which integers meet this lucky condition.

Return the largest lucky integer found in arr. If no integers satisfy this condition, return -1. For example, in arr = [2,2,3,4], only 2 appears exactly twice, so 2 is the lucky integer.

Examples

Example 1

Input: arr = [2,2,3,4]

Output: 2

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

1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3

Input: arr = [2,2,2,3,3]

Output: -1

There are no lucky numbers in the array.

Constraints

1 <= arr.length <= 500
1 <= arr[i] <= 500

Solution Approach

Frequency Counting with Hash Table

Traverse arr and build a hash table where keys are integers and values are their counts. This maps every integer to its frequency and prepares for quick comparison.

Scan for Lucky Integers

Iterate over the hash table entries and collect integers where the value matches the frequency. Keep track of the maximum to return the largest lucky integer efficiently.

Edge Case Handling

Ensure that arrays with no lucky integers return -1. Handle duplicates and multiple lucky integers by always updating the maximum found during the scan.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) to count frequencies plus O(n) to scan entries, yielding O(n) overall. Space complexity is O(n) for the hash table storing counts of integers up to the array length.

What Interviewers Usually Probe

Do you count the frequency of each integer efficiently?
Have you considered returning the largest lucky integer instead of the first match?
Are you handling arrays where no lucky integer exists correctly?

Common Pitfalls or Variants

Common pitfalls

Assuming the first matching integer is the largest without scanning all counts.
Forgetting to check multiple integers when several satisfy the lucky condition.
Not handling arrays with no lucky integers, returning an incorrect default.

Follow-up variants

Find all lucky integers instead of only the largest.
Determine lucky integers under constraints with very large arrays.
Modify the problem to find the smallest lucky integer rather than the largest.

FAQ

What is a lucky integer in this problem?

A lucky integer is a number whose value equals its frequency in the array.

Can there be multiple lucky integers?

Yes, but you should return only the largest one according to the problem requirement.

What should I return if no lucky integer exists?

Return -1 if the array contains no integers that match their frequency.

Which data structure is best for counting frequencies?

A hash table works best, mapping each integer to its count for constant-time lookup.

Does this solution rely on array scanning plus hash lookup?

Yes, counting frequencies and then comparing values with counts is the core array scanning plus hash lookup pattern for this problem.

terminal

Solution

Solution 1: Counting

We can use a hash table or an array $\textit{cnt}$ to count the occurrences of each number in $\textit{arr}$. Then, we iterate through $\textit{cnt}$ to find the largest $x$ such that $\textit{cnt}[x] = x$. If there is no such $x$, return $-1$.

1

2

3

4

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        return max((x for x, v in cnt.items() if x == v), default=-1)

Continue Practicing

#1366 rank teams by votes #1481 least number of unique integers after k removals #1497 check if array pairs are divisible by k