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 largestlucky integer in the array. If there is no lucky integer return -1.

Examples

Example 1

1
2
3

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2

1
2
3

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

1
2
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

Solution

Method 1 – Frequency Counting

Intuition

We can count the frequency of each number in the array, then check which numbers have a frequency equal to their value. The largest such number is the answer. This works because the constraints are small and counting is efficient.

Approach

  1. Initialize a frequency array or hash map to count occurrences of each number.
  2. Iterate through the array and update the frequency count for each number.
  3. Iterate through the frequency map and for each number, if its frequency equals its value, track the maximum such number.
  4. Return the largest lucky number found, or -1 if none exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int freq[501] = {0};
        for (int n : arr) freq[n]++;
        int ans = -1;
        for (int i = 1; i <= 500; ++i) {
            if (freq[i] == i) ans = i;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func findLucky(arr []int) int {
    freq := make([]int, 501)
    for _, n := range arr {
        freq[n]++
    }
    ans := -1
    for i := 1; i <= 500; i++ {
        if freq[i] == i {
            ans = i
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int findLucky(int[] arr) {
        int[] freq = new int[501];
        for (int n : arr) freq[n]++;
        int ans = -1;
        for (int i = 1; i <= 500; i++) {
            if (freq[i] == i) ans = i;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun findLucky(arr: IntArray): Int {
        val freq = IntArray(501)
        for (n in arr) freq[n]++
        var ans = -1
        for (i in 1..500) {
            if (freq[i] == i) ans = i
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def findLucky(self, arr: list[int]) -> int:
        freq = [0] * 501
        for n in arr:
            freq[n] += 1
        ans = -1
        for i in range(1, 501):
            if freq[i] == i:
                ans = i
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut freq = vec![0; 501];
        for n in arr {
            freq[n as usize] += 1;
        }
        let mut ans = -1;
        for i in 1..=500 {
            if freq[i] == i as i32 {
                ans = i as i32;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    findLucky(arr: number[]): number {
        const freq = new Array(501).fill(0);
        for (const n of arr) freq[n]++;
        let ans = -1;
        for (let i = 1; i <= 500; i++) {
            if (freq[i] === i) ans = i;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of arr, as we scan the array and then a fixed range.
  • 🧺 Space complexity: O(1), since the frequency array size is constant (501).