Find Lucky Integer in an Array | LeetCode Problems And Solution

Find Lucky Integer in an Array is an easy LeetCode problem built around one of the most common tools in coding interviews: a frequency count. You count how many times each value appears and then compare that count with the value itself. If you can write this quickly and pick the right data structure for the given limits, you will handle a whole family of similar questions (first unique character, majority element, anagram checks).

The small twist here is that you need the largest lucky number, and the constraints are small enough that you can skip the HashMap entirely. Spotting that is the interesting part.

Problem

Call a number in an array "lucky" if it appears in the array exactly as many times as its own value. For example, 3 is lucky if the array contains exactly three 3s. Given an integer array arr, return the biggest lucky number. If no number is lucky, return -1.

Input: an integer array arr.

Output: one integer, the largest lucky number, or -1.

Constraints: 1 ≤ arr.length ≤ 500, and 1 ≤ arr[i] ≤ 500.

Input: arr = [2,2,3,4]
Output: 2
(2 appears twice. 3 and 4 appear once each.)

Input: arr = [1,2,2,3,3,3]
Output: 3
(1, 2 and 3 are all lucky. The largest is 3.)

Input: arr = [2,2,2,3,3]
Output: -1

Approach

The question has two parts: "how often does each value appear?" and "which value has a count equal to itself, and which is the biggest?".

1. Count. Since every value is between 1 and 500, you can use a plain int[] count = new int[501] where count[v] is how many times v appears. One pass over the array fills it.
2. Search from the top. Loop v from 500 down to 1. The first v where count[v] == v is the largest lucky number, so return it right away.
3. If the loop ends without finding one, return -1.

Why loop from the top? Because the problem wants the maximum. Going downward means the first match is already the answer and you can stop early. Going upward would force you to keep a running max and finish the whole loop.

A HashMap would also work and is the general solution when values can be huge or negative. But here the array index acts as a ready-made hash, and it avoids boxing every int into an Integer.

Dry run with [1,2,2,3,3,3]: after counting, count[1] = 1, count[2] = 2, count[3] = 3, and everything else is 0. Going down from 500, all values above 3 have count 0, which is never equal to a positive v. At v = 3, count[3] = 3, so return 3.

Solution in Java

class Solution {
    public int findLucky(int[] arr) {
        // Values are between 1 and 500, so a plain array works as a frequency table
        int[] count = new int[501];
        for (int x : arr) {
            count[x]++;
        }
        // Walk from the biggest value down; the first lucky one is the answer
        for (int v = 500; v >= 1; v--) {
            if (count[v] == v) {
                return v;
            }
        }
        return -1;
    }

    // Small driver for local testing
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] tests = {
            {2, 2, 3, 4}, {1, 2, 2, 3, 3, 3}, {2, 2, 2, 3, 3}, {5}, {7, 7, 7, 7, 7, 7, 7}, {1}, {3, 3, 3, 3}
        };
        for (int[] t : tests) {
            System.out.println(java.util.Arrays.toString(t) + " -> " + s.findLucky(t));
        }
    }
}

On LeetCode you submit only the findLucky method. The main method is for running it on your own machine. The old solution on this page used a HashMap and a Math.max over all keys, which is correct. The version above is shorter and faster for these limits.

Tests I ran, including the official examples:

• [5] gives -1. 5 appears once, not five times.
• [7,7,7,7,7,7,7] gives 7.
• [1] gives 1, the smallest possible lucky number.
• [3,3,3,3] gives -1. Appearing more times than the value does not count.

Output

[2, 2, 3, 4] -> 2
[1, 2, 2, 3, 3, 3] -> 3
[2, 2, 2, 3, 3] -> -1
[5] -> -1
[7, 7, 7, 7, 7, 7, 7] -> 7
[1] -> 1
[3, 3, 3, 3] -> -1

Complexity

Time: O(n + M), where n is the array length and M = 500 is the value range. One pass to count and at most one pass over the count array.

Space: O(M) for the count array, which is a fixed 501 ints no matter how big the input is.

Variations

• Values not bounded. If values could be up to 10⁹ or negative, use a HashMap<Integer, Integer> with merge(x, 1, Integer::sum), then scan the entries.
• Return all lucky numbers. Loop the count array and collect every v with count[v] == v into a list.
• Smallest lucky number. Loop from 1 upward instead and return the first match.
• Tighter bound. A value v can only be lucky if it appears v times, so v can never be bigger than the array length. You can start the downward loop at min(500, arr.length).

More easy LeetCode problems on the site: Detect Capital and Shuffle String.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More LeetCode solutions All coding problems MCQ practice