Code Implementation

class Solution:
    def findLucky(self, arr):
        from collections import Counter
        freq = Counter(arr)
        lucky = -1
        for num, count in freq.items():
            if num == count:
                lucky = max(lucky, num)
        return lucky
      

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int n : arr) freq[n]++;
        int lucky = -1;
        for (auto& p : freq) {
            if (p.first == p.second) lucky = max(lucky, p.first);
        }
        return lucky;
    }
};
      

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : arr) freq.put(n, freq.getOrDefault(n, 0) + 1);
        int lucky = -1;
        for (int key : freq.keySet()) {
            if (key == freq.get(key)) lucky = Math.max(lucky, key);
        }
        return lucky;
    }
}
      

var findLucky = function(arr) {
    let freq = {};
    for (let n of arr) freq[n] = (freq[n] || 0) + 1;
    let lucky = -1;
    for (let num in freq) {
        if (parseInt(num) === freq[num]) lucky = Math.max(lucky, parseInt(num));
    }
    return lucky;
};
      

Problem Description

Given an array of integers arr, find the largest "lucky" integer in the array. A lucky integer is defined as an integer whose value is exactly equal to its frequency in the array (i.e., the number appears in the array exactly as many times as its value). If there is no lucky integer, return -1.

Key constraints:

• Only one valid answer is needed (the largest lucky integer).
• If there are multiple lucky integers, return the largest one.
• If no lucky integer exists, return -1.
• Elements can be reused for counting, but not for different lucky values.

Thought Process

The core of the problem is to find an integer in the array such that its value is equal to the number of times it appears.

The brute-force way would be to check, for every unique number in the array, how many times it occurs, and then see if that count matches the number itself. However, this would require nested loops and be inefficient for large arrays.

To optimize, we can use a frequency map (hash table) to count the occurrences of each number in a single pass. This way, we can quickly check for each unique number if its frequency equals its value. Since we want the largest such integer, we keep track of the maximum one found.

This shift from brute-force to using a hash map is key for efficiency, reducing repeated counting and speeding up the solution.

Solution Approach

We'll solve the problem with these clear steps:

1. Count Frequencies: Use a hash map (dictionary) to record how many times each number appears in the array. This can be done in a single loop.
2. Check for Lucky Integers: Go through each key-value pair in the frequency map. For each number, if its value (the count) matches the number itself, it's a candidate.
3. Track the Largest: Since we need the largest lucky integer, we keep updating a variable if we find a bigger lucky integer.
4. Return the Result: If no lucky integer is found, return -1. Otherwise, return the largest lucky integer found.

We use a hash map because it allows us to count frequencies and check values in constant time per operation, making the algorithm efficient.

Example Walkthrough

Let's walk through an example with arr = [2,2,3,4]:

1. Count frequencies:
   • 2 appears 2 times
   • 3 appears 1 time
   • 4 appears 1 time
2. Check each number:
   • 2: Its frequency is 2, and its value is 2. So, 2 is a lucky integer.
   • 3: Its frequency is 1, which does not equal 3.
   • 4: Its frequency is 1, which does not equal 4.
3. Find the largest lucky integer:
   • Only 2 qualifies. So, the answer is 2.

If the input was arr = [1,2,2,3,3,3]:

• 1 appears 1 time (lucky), 2 appears 2 times (lucky), 3 appears 3 times (lucky).
• The largest is 3, so we return 3.

Time and Space Complexity

Brute-force approach:

• For each unique number, count its occurrences (O(n) per number).
• If there are k unique numbers, total time is O(n*k), which can be O(n^2) in the worst case.
• Space: O(1) if no extra data structures used.

• Counting frequencies with a hash map: O(n), where n is the length of the array.
• Checking each unique number: O(k), where k is the number of unique numbers (k ≤ n).
• Total time: O(n).
• Space: O(k) for the hash map.

The optimized approach is much faster and uses extra space for the frequency map, but this is acceptable for most applications.

Summary

To solve the "Find Lucky Integer in an Array" problem, we leveraged a hash map to efficiently count the frequency of each integer. By comparing each number's value to its frequency, we identified all "lucky" integers and selected the largest one. This approach is both time and space efficient, and demonstrates the power of hash maps for frequency counting problems. The solution is simple, elegant, and scales well even for large arrays.