Find Lucky Integer in an Array

Problem Statement

In the given task, we have an array of integers referred to as arr. The goal is to identify a lucky integer within this array. A lucky integer is defined as an integer that appears in the array a number of times equal to its own value. Our task is not just to find any lucky integer, but the largest lucky integer in the array. If no such lucky integer exists, the function should return -1. This problem leverages the concepts of frequency counting within arrays and checking these frequencies against the values themselves.

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.

Example 3

Input:

arr = [2,2,2,3,3]

Output:

-1

Explanation:

There are no lucky numbers in the array.

Constraints

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

Approach and Intuition

The given examples and constraints streamline our approach towards finding a lucky integer in a feasible manner:

1. Understanding the Problem through Examples:

   • From Example 1 with input arr = [2,2,3,4], the integer 2 is lucky because it appears 2 times, which matches its value. There's no number greater than 2 that satisfies the condition, hence the output is 2.
   • Example 2 demonstrates multiple lucky integers, with arr = [1,2,2,3,3,3] where 1, 2, and 3 are all lucky integers. However, we are required to return the largest which is 3.
   • Example 3 where the input is arr = [2,2,2,3,3] shows an edge case where no numbers in the array have the same count as their value, yielding an output of -1.

2. Approach:

   • The first step is to determine the frequency of each integer in the array. This can be efficiently done using a hashmap or using an array of size 501 (given max constraints) to keep a simple count of each integer from 1 to 500.
   • The next step involves iterating through our frequency structure and checking: if the count of any integer i is equal to i itself.
   • Throughout the iteration, keep track of the maximum integer value that satisfies the lucky integer condition.
   • If found, return the maximum lucky integer; otherwise, return -1.

By utilizing the constraints given, we can infer that our approach will efficiently run within acceptable limits, allowing us to handle the upper constraint effortlessly with the chosen method of frequency counting. This strategic approach not only simplifies the problem but ensures a speedy and correct determination of the largest lucky integer if it exists.

Solutions

public int findLuckyNumber(int[] numbers) {
    Map<Integer, Integer> frequency = new HashMap<>();
    for (int num : numbers) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    
    int maxLucky = -1;
    for (Map.Entry<Integer, Integer> item : frequency.entrySet()) {
        if (item.getKey().equals(item.getValue())) {
            maxLucky = Math.max(maxLucky, item.getKey());
        }
    }
    
    return maxLucky;
}