Find Lucky Integer in an Array — Problem & Solution
Find Lucky Integer in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Find Lucky Integer in an Array is an easy coding problem on arrays, hash table and counting, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An integer is lucky if its value equals the number of times it appears in the array.
Given an array of integers arr, return the largest lucky integer, or -1 if none exists.
Example 1
Input: arr = [2,2,3,4]
Output: 2
Explanation: 2 appears exactly twice.
Example 2
Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky; the largest is 3.
Example 3
Input: arr = [2,2,2,3,3]
Output: -1
Explanation: 2 appears three times and 3 appears twice.
Constraints
1 <= arr.length <= 5001 <= arr[i] <= 500
Hints for Find Lucky Integer in an Array
Hint 1
Count how many times each value appears.
Hint 2
A value
vis lucky exactly whencount[v] == v.Hint 3
Scan the counts and keep the largest lucky value;
-1if none matched.
How to solve Find Lucky Integer in an Array
The definition is a direct test on a frequency table, so one counting pass and one scan finish the job.
Approach
- Build a frequency map (or, since values are bounded by 500, a fixed-size array).
- Walk the distinct values; whenever
count[v] == v, considervas a candidate. - Return the largest candidate, or
-1if there were none.
Why it works
Every lucky number must appear in the frequency table, so scanning the table considers all of them exactly once.
Complexity
- Time —
O(n + V) where V is the value range - Space —
O(V)
Pitfalls
- Returning the first lucky value found gives the smallest, not the largest.
- Scanning values downward from the maximum lets you return early — but only if you scan the value range, not the array order.
Reference solution
Python
from typing import List
def findLucky(arr: List[int]) -> int:
count = {}
for x in arr:
count[x] = count.get(x, 0) + 1
best = -1
for v, c in count.items():
if c == v and v > best:
best = v
return bestJava
public static int findLucky(int[] arr) {
int[] count = new int[501];
for (int x : arr) count[x]++;
int best = -1;
for (int v = 1; v <= 500; v++) {
if (count[v] == v && v > best) best = v;
}
return best;
}C++
int findLucky(vector<int>& arr) {
vector<int> count(501, 0);
for (int x : arr) count[x]++;
int best = -1;
for (int v = 1; v <= 500; v++) {
if (count[v] == v && v > best) best = v;
}
return best;
}JavaScript
var findLucky = function(arr) {
const count = {};
for (let i = 0; i < arr.length; i++) {
const key = String(arr[i]);
count[key] = (count[key] || 0) + 1;
}
let best = -1;
const keys = Object.keys(count);
for (let i = 0; i < keys.length; i++) {
const v = Number(keys[i]);
if (count[keys[i]] === v && v > best) best = v;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets