Find Lucky Integer in an Array

Easy
491.

Find Lucky Integer in an Array

Find Lucky Integer in an Array is an easy coding problem on arrays, hash table and counting, asked in Amazon interviews.

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 <= 500
  • 1 <= arr[i] <= 500
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var findLucky = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 500
  • 1 <= arr[i] <= 500

Hints for Find Lucky Integer in an Array

  1. Hint 1

    Count how many times each value appears.

  2. Hint 2

    A value v is lucky exactly when count[v] == v.

  3. Hint 3

    Scan the counts and keep the largest lucky value; -1 if 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

  1. Build a frequency map (or, since values are bounded by 500, a fixed-size array).
  2. Walk the distinct values; whenever count[v] == v, consider v as a candidate.
  3. Return the largest candidate, or -1 if 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 best

Java

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