Find Lucky Integer in an Array

easy hashing hash table frequency count

Problem

Given an array of integers arr, a lucky integer is a value whose frequency in the array equals the value itself. Return the largest lucky integer; if none exists, return -1.

Inputarr = [1,2,2,3,3,3]

Output3

1 appears once, 2 appears twice, 3 appears three times — all three are lucky, so return the largest, 3.

Inputarr = [2,2,2,3,3]

Output-1

2 appears 3 times and 3 appears 2 times, so no value matches its own frequency.

arr (comma-separated)

def find_lucky(arr):
    count = {}
    for x in arr:
        count[x] = count.get(x, 0) + 1
    lucky = -1
    for v, c in count.items():
        if v == c:
            lucky = max(lucky, v)
    return lucky

function findLucky(arr) {
  const count = new Map();
  for (const x of arr) {
    count.set(x, (count.get(x) || 0) + 1);
  }
  let lucky = -1;
  for (const [v, c] of count) {
    if (v === c) {
      lucky = Math.max(lucky, v);
    }
  }
  return lucky;
}

int findLucky(int[] arr) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : arr) {
        count.put(x, count.getOrDefault(x, 0) + 1);
    }
    int lucky = -1;
    for (Map.Entry<Integer, Integer> e : count.entrySet()) {
        if (e.getKey().equals(e.getValue())) {
            lucky = Math.max(lucky, e.getKey());
        }
    }
    return lucky;
}

int findLucky(vector<int>& arr) {
    unordered_map<int, int> count;
    for (int x : arr) {
        count[x]++;
    }
    int lucky = -1;
    for (auto& [v, c] : count) {
        if (v == c) {
            lucky = max(lucky, v);
        }
    }
    return lucky;
}

Explanation

A lucky integer is one whose count equals its value. To check that for every candidate we first need to know how often each value occurs, which is a textbook job for a hash map used as a frequency table.

Phase 1 — count. We sweep the array once and, for each element x, increment count[x]. After this pass the map holds value → frequency for every distinct number, built in O(n) total time because each hash insertion or update is O(1) on average.

Phase 2 — scan. We start with lucky = -1 and walk the map's entries. Whenever a value v has frequency c with v == c, it is lucky, so we update lucky = max(lucky, v). Taking the maximum lets us keep the largest lucky value even though map iteration order is arbitrary.

If no entry ever satisfies v == c, lucky stays -1, which is exactly the answer the problem asks for in that case.

For arr = [1,2,2,3,3,3] the map becomes {1:1, 2:2, 3:3}. All three entries are lucky, and the maximum among them is 3.

Time: O(n) Space: O(n)