LeetCode 1394 - Find Lucky Integer in an Array

LeetCode Problem 1394

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

This problem asks us to identify a special number in an array called a lucky integer. A lucky integer is defined as an integer in the array whose frequency exactly matches its value. For example, if the number 3 appears exactly 3 times in the array, it is considered lucky. Our task is to find the largest lucky integer. If no lucky integers exist, we return -1.

The input is a list of integers arr with constraints 1 <= arr.length <= 500 and 1 <= arr[i] <= 500. These constraints indicate the array is small enough for solutions with quadratic or linear time complexity. The integers are positive and bounded, which simplifies frequency counting. Important edge cases include arrays with no lucky integers, arrays where multiple integers are lucky, and arrays where the maximum lucky integer occurs at the end or beginning of the array.

Approaches

Brute Force

A brute-force approach is to iterate through every unique number in the array, count its occurrences, and check if that count matches the number itself. We track the largest lucky integer during this process. This works because it directly checks the definition of a lucky integer.

However, counting occurrences by scanning the array for each unique number results in O(n^2) time complexity. For an array of size 500, this may still work but is inefficient compared to linear solutions.

Optimal Approach

The optimal approach leverages a hash map (dictionary) to count the frequency of each number in a single pass. Once frequencies are recorded, we iterate through the map and identify all numbers whose frequency equals the number itself. Returning the largest among them gives the correct result. This approach is linear in time O(n) and uses O(n) space for the hash map.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Count frequency of each number by scanning the array repeatedly
Optimal	O(n)	O(n)	Use a hash map to count frequencies and find largest lucky integer

Algorithm Walkthrough

1. Initialize an empty dictionary called freq to store the frequency of each number.

2. Iterate over the array arr. For each number num, increment its count in freq.

3. Initialize a variable largest_lucky to -1. This will store the largest lucky integer found.

4. Iterate through the dictionary freq. For each num and its count:

5. Check if the count equals the number itself.

6. If it does and it is larger than largest_lucky, update largest_lucky with this number.

7. Return largest_lucky.

Why it works: The hash map ensures each number's frequency is accurately tracked. Checking each entry guarantees that we identify all lucky integers, and comparing to largest_lucky ensures we return the largest one.

Python Solution

from typing import List

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1
        
        largest_lucky = -1
        for num, count in freq.items():
            if num == count and num > largest_lucky:
                largest_lucky = num
                
        return largest_lucky

In this Python implementation, we first build a frequency dictionary using dict.get to handle missing keys. Then, we scan all key-value pairs to check the lucky condition and update the largest lucky integer.

Go Solution

func findLucky(arr []int) int {
    freq := make(map[int]int)
    for _, num := range arr {
        freq[num]++
    }
    
    largestLucky := -1
    for num, count := range freq {
        if num == count && num > largestLucky {
            largestLucky = num
        }
    }
    
    return largestLucky
}

In Go, we use a map to count frequencies and a variable largestLucky to track the largest lucky integer. The iteration and comparison logic mirrors the Python version, with Go-specific syntax for map access and iteration.

Worked Examples

Example 1: arr = [2,2,3,4]

Step	Action	freq	largest_lucky
1	Count 2	{2:1}	-1
2	Count 2	{2:2}	-1
3	Count 3	{2:2, 3:1}	-1
4	Count 4	{2:2, 3:1, 4:1}	-1
5	Check lucky numbers	2 matches count 2	2
6	Check 3 and 4	no match	2

Output: 2

Example 2: arr = [1,2,2,3,3,3]

Step	freq	largest_lucky
Count numbers	{1:1, 2:2, 3:3}	-1
Check lucky numbers	1, 2, 3	3

Output: 3

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

Step	freq	largest_lucky
Count numbers	{2:3, 3:2}	-1
Check lucky numbers	none match	-1

Output: -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass to count frequencies, then iterate dictionary (size ≤ n)
Space	O(n)	Dictionary stores frequency of up to n unique numbers

The reasoning is straightforward: each array element is processed once for counting and the frequency dictionary contains at most n entries.

Test Cases

# Provided examples
assert Solution().findLucky([2,2,3,4]) == 2  # single lucky number
assert Solution().findLucky([1,2,2,3,3,3]) == 3  # multiple lucky numbers, return largest
assert Solution().findLucky([2,2,2,3,3]) == -1  # no lucky number

# Additional cases
assert Solution().findLucky([1]) == 1  # smallest array, lucky
assert Solution().findLucky([500]*500) == 500  # max value array, lucky
assert Solution().findLucky([1,1,2,2,2,3,3,3,3]) == 3  # multiple lucky numbers
assert Solution().findLucky([4,4,4,4,5,5,5,5,5]) == 5  # largest lucky at end
assert Solution().findLucky([6,6,6,6,6]) == -1  # frequency does not match any value

Test	Why
[2,2,3,4]	single lucky number
[1,2,2,3,3,3]	multiple lucky numbers, must return largest
[2,2,2,3,3]	no lucky number
[1]	smallest possible array
[500]*500	largest number and array, stress test
[1,1,2,2,2,3,3,3,3]	multiple lucky numbers
[4,4,4,4,5,5,5,5,5]	largest lucky at end
[6,6,6,6,6]	frequency does not match value

Edge Cases

Single element array: If the array has only one element, it is lucky only if it is 1. Our implementation handles this correctly by counting the frequency of that single element.

All elements identical: When all numbers are the same, the lucky integer exists only if the count equals that number. Both Python and Go solutions correctly compute the count and compare with the value.

Multiple lucky integers: Arrays may contain several lucky integers. The algorithm must return the largest, not the first found. This is ensured by tracking largest_lucky and updating it only when a larger valid number is found.

This solution correctly handles all edge cases, scales within the constraints, and ensures the largest lucky integer is returned.