# Find Lucky Integer in an Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-lucky-integer-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-lucky-integer-in-an-array
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
---
## Problem
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`.

**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`

# Approaches
## Brute Force with Nested Loops
This approach involves iterating through each element of the array and for each element, counting its occurrences by iterating through the array again. This is the most straightforward but least efficient method.
**Time:** O(N^2), where N is the number of elements in the array. The nested loops cause us to perform N * N comparisons. · **Space:** O(1), as we only use a few variables to store the count and the result, regardless of the input size.
**Pros:** Simple to understand and implement.; Requires no extra space (O(1) space complexity).
**Cons:** Very inefficient for large arrays, with a quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for larger inputs.
### Explanation
The brute-force method checks every number in the array to see if it's a lucky number. For each number `x` at index `i`, we perform a full scan of the array to count how many times `x` appears. If this count is equal to the value of `x`, we compare it with the largest lucky number found so far and update it if `x` is larger. This process is repeated for all numbers in the array.

```java
class Solution {
    public int findLucky(int[] arr) {
        int largestLucky = -1;
        // Using a Set to only check unique numbers can be a small optimization,
        // but the core complexity remains the same if we recount for each.
        for (int i = 0; i < arr.length; i++) {
            int count = 0;
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] == arr[i]) {
                    count++;
                }
            }
            if (count == arr[i]) {
                largestLucky = Math.max(largestLucky, arr[i]);
            }
        }
        return largestLucky;
    }
}
```
### Algorithm
- Initialize a variable `largestLucky` to -1.
- Iterate through the input array `arr` with an outer loop from index `i = 0` to `n-1`.
- For each element `arr[i]`, initialize a `count` to 0.
- Start an inner loop from index `j = 0` to `n-1` to count the occurrences of `arr[i]`.
- If `arr[j]` is equal to `arr[i]`, increment `count`.
- After the inner loop completes, check if `count` is equal to the value `arr[i]`.
- If they are equal, it means `arr[i]` is a lucky number. Update `largestLucky` to be the maximum of its current value and `arr[i]`.
- After the outer loop completes, return `largestLucky`.

## Sorting the Array
This method improves upon the brute-force approach by first sorting the array. Sorting groups identical elements together, which allows for efficient frequency counting in a single subsequent pass over the sorted array.
**Time:** O(N log N), which is dominated by the sorting step. The subsequent scan to count frequencies is O(N). · **Space:** O(log N) to O(N). This depends on the space used by the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Significantly more efficient than the brute-force approach.; Conceptually simple after the sorting step.
**Cons:** The time complexity is limited by the sorting algorithm, which is not as fast as a linear scan.; The space complexity depends on the sorting algorithm's implementation and might not be O(1).
### Explanation
By sorting the array, all equal elements become adjacent. This allows us to count the frequency of each number in a single pass. We can iterate through the array, and for each distinct number, we count how many times it appears consecutively. If this count matches the number's value, we identify it as a lucky number and update our potential answer. Since we process numbers in increasing order, the last lucky number we find will be the largest one.

```java
import java.util.Arrays;

class Solution {
    public int findLucky(int[] arr) {
        Arrays.sort(arr);
        int largestLucky = -1;
        int i = 0;
        while (i < arr.length) {
            int j = i;
            while (j < arr.length && arr[j] == arr[i]) {
                j++;
            }
            int count = j - i;
            if (count == arr[i]) {
                largestLucky = arr[i]; // Last lucky number found will be the largest
            }
            i = j;
        }
        return largestLucky;
    }
}
```
### Algorithm
- Sort the input array `arr` in non-decreasing order.
- Initialize `largestLucky` to -1.
- Iterate through the sorted array using a pointer `i`.
- At each position `i`, find the end of the contiguous block of the same number `arr[i]`. Let's say this block ends at index `j-1`.
- The frequency of `arr[i]` is `j - i`.
- If the frequency `(j - i)` is equal to the value `arr[i]`, then `arr[i]` is a lucky number. Update `largestLucky` with `arr[i]`.
- Move the pointer `i` to `j` to start checking the next distinct number.
- Repeat until the end of the array is reached.
- Return `largestLucky`.

## Using a Hash Map
A more direct way to find frequencies is to use a hash map. We can iterate through the array once to populate the map with number-frequency pairs, and then iterate through the map to find lucky numbers.
**Time:** O(N), where N is the number of elements. The first loop to build the map takes O(N) time. The second loop iterates through the unique elements (at most N), taking O(U) time where U <= N. Total time is O(N + U) which simplifies to O(N). · **Space:** O(U), where U is the number of unique elements in the array. In the worst case, all elements are unique, so the space complexity is O(N).
**Pros:** Achieves linear time complexity, O(N), which is very efficient.; Works for any range of integer values, not just a constrained set.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst case where all elements are unique.
### Explanation
This approach uses a hash map to efficiently count the frequency of each number in the array. We traverse the input array once, and for each number, we increment its corresponding count in the map. After building the frequency map, we iterate through its key-value pairs. If a key (the number) is equal to its value (the frequency), we've found a lucky number. We keep track of the largest such number found.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int largestLucky = -1;
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            int num = entry.getKey();
            int freq = entry.getValue();
            if (num == freq) {
                largestLucky = Math.max(largestLucky, num);
            }
        }
        return largestLucky;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` to store the frequency of each number.
- Iterate through the input array `arr`. For each `num` in `arr`, update its count in the hash map.
- Initialize `largestLucky` to -1.
- Iterate through the entries of the hash map. For each entry `(key, value)`:
- Check if the number (`key`) is equal to its frequency (`value`).
- If `key == value`, it's a lucky number. Update `largestLucky = Math.max(largestLucky, key)`.
- After checking all entries, return `largestLucky`.

## Using a Frequency Array
Given the constraint that array values are between 1 and 500, we can use a simple array as a frequency counter instead of a hash map. This is often faster and more space-efficient for a constrained range of integer values.
**Time:** O(N + M), where N is the length of `arr` and M is the maximum possible value (500). The first loop takes O(N) and the second loop takes O(M). This is effectively linear time. · **Space:** O(M), for the frequency array, where M is the maximum possible value (501). Since M is a constant, this is considered O(1) constant space.
**Pros:** The most efficient approach in both time and space for the given constraints.; Avoids the overhead of hashing and uses constant extra space.; Very fast in practice due to direct array access and good cache locality.
**Cons:** This approach is only applicable because the range of values in the input array is small and known beforehand.; It would be inefficient or infeasible if the numbers could be very large.
### Explanation
This is an optimization of the hash map approach, tailored to the problem's constraints. Since we know the numbers are all within the range [1, 500], we can use a fixed-size array (of size 501) to store frequencies. The index of the array corresponds to the number, and the value at that index is its frequency. After populating this frequency array in one pass, we can perform a second pass. To find the largest lucky number efficiently, we iterate downwards from 500 to 1. The first index `i` we find where `counts[i] == i` will be our answer.

```java
class Solution {
    public int findLucky(int[] arr) {
        int[] counts = new int[501]; // Constraints: 1 <= arr[i] <= 500
        for (int num : arr) {
            counts[num]++;
        }

        for (int i = 500; i >= 1; i--) {
            if (counts[i] == i) {
                return i; // Found the largest lucky number
            }
        }

        return -1; // No lucky number found
    }
}
```
### Algorithm
- Create an integer array `counts` of size 501 (since values are from 1 to 500).
- Iterate through the input array `arr`. For each `num`, increment `counts[num]`.
- To find the largest lucky number, iterate from `i = 500` down to `1`.
- At each `i`, check if `counts[i]` is equal to `i`.
- If `counts[i] == i`, then `i` is a lucky number. Since we are iterating downwards, this is the largest one. Return `i` immediately.
- If the loop completes without finding any lucky number, return -1.

# Solutions
### Java

```java
class Solution { public int findLucky ( int [] arr ) { int [] cnt = new int [ 510 ]; for ( int x : cnt ) { ++ cnt [ x ]; } int ans = - 1 ; for ( int x = 1 ; x < cnt . length ; ++ x ) { if ( cnt [ x ] == x ) { ans = x ; } } return ans ; } }
```

### Python

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

### CPP

```cpp
class Solution { public: int findLucky ( vector < int >& arr ) { int cnt [ 510 ]; memset ( cnt , 0 , sizeof ( cnt )); for ( int x : arr ) { ++ cnt [ x ]; } int ans = - 1 ; for ( int x = 1 ; x < 510 ; ++ x ) { if ( cnt [ x ] == x ) { ans = x ; } } return ans ; } };
```