Find the Lucky Integer in an Array

Problem Statement

Given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value.

Return the largest lucky integer in the array. If there is no lucky integer return -1.

LeetCode:

Find Lucky Number in an Array

Examples

Example 1:

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

Explanation: 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

Explanation: 1, 2, and 3 are all lucky numbers, return the largest of them, which is 3.

Example 3:

Input: arr = [2, 2, 2, 3, 3]
Output: -1

Explanation: There are no lucky number in the array.

Constraints:

• 1 ≤ arr.length ≤ 500
• 1 ≤ arr[i] ≤ 500

Different Approaches

1️⃣ Hash Map Frequency Count

Intuition:

• Use a hash map to count occurrences of each element.
• Traverse the map and find the maximum key where key == frequency.

Approach:

1. Use unordered_map<int, int> to store frequencies.
2. Iterate through the map and check key == value.
3. Track the maximum lucky number found.

Code:

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> freq;

        for (int num : arr) {
            freq[num]++;
        }

        int maxLucky = -1;
        for (auto [num, count] : freq) {
            if (num == count) {
                maxLucky = max(maxLucky, num);
            }
        }

        return maxLucky;
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • One pass for count, and one for check.
• Space Complexity:O(n)
  • For hash map (in worst case, all values are unique).

2️⃣ Fixed Size Frequency Array (Optimize for Small Range)

Intuition:

According to the constraints: 1 ≤ arr[i] ≤ 500.

So we can use a fixed array of size 501 to count frequency (no hash map needed).

Approach:

1. Declare int freq[501] = {0};.
2. Count frequency of each number.
3. From highest (500 → 1), return the first index where freq[i] == i.

Code:

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int freq[501] = {0};

        for (int num : arr) {
            freq[num]++;
        }

        for (int i = 500; i >= 1; --i) {
            if (freq[i] == i) {
                return i;
            }
        }

        return -1;
    }
};

Complexity Analysis:

• Time Complexity:O(n + 500) = O(n)
• Space Complexity:O(1)
  •  Constant size array (501 elements)

3️⃣ Sorting + Frequency Counting

Intuition:

• Sort the array.
• Traverse it and count frequencies.
• Whenever count == value, check if it's the maximum lucky number.

Approach:

1. Sort the array.
2. Traverse the sorted array while counting consecutive equal numbers.
3. Compare count with the number.

Code:

class Solution {
public:
    int findLucky(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int maxLucky = -1;
        int i = 0;
        int n = arr.size();

        while (i < n) {
            int num = arr[i];
            int count = 0;

            while (i < n && arr[i] == num) {
                count++;
                i++;
            }

            if (count == num) {
                maxLucky = max(maxLucky, num);
            }
        }

        return maxLucky;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n)
  • Due to sorting.
• Space Complexity:O(1)
  • If in-place sorting.