Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Whether an integer is lucky depends only on its total frequency, not on where it appears. A frequency map lets us test each distinct value once and choose the greatest value whose frequency equals itself.

Approach

Count all array values. Initialize the answer to -1, then inspect each value and its count. If they are equal, maximize the answer with that value; the code may equivalently use its count because equality has already been checked. Return the answer after inspecting every key. Keeping a maximum is necessary because several different lucky integers may exist.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        map = defaultdict(int)
        for x in arr:
            map[x] += 1

        res = -1
        for k in map:
            if map[k] == k:
                res = max(res, map[k])

        return res

Complexity analysis

For n values and u distinct values, counting and checking frequencies takes O(n + u) expected time and O(u) auxiliary space.