💬 Discord
Sign In
NeetCode #61LC-1394EasyArrays & Hashing
← Back to All Problems

#61 · #1394 · Find Lucky Integer in an Array(找出数组中的幸运数)

📌 Problem Statement & Constraints

Given an array of integers arr, a lucky integer is one whose value equals its frequency in the array. Return the largest lucky integer, or -1 if none exists. Constraints: 1 <= arr.length <= 500, 1 <= arr[i] <= 500.

💡 Core Algorithmic Approaches

  1. Count the frequency of each value, then check the condition value == frequency.
  2. Track the maximum value satisfying the condition; initialise to -1 to cover the no-lucky-integer case.
  3. Since the value range is bounded by 500, a counting array indexed by value is a natural O(n + V) alternative to a hash map.
  4. Iterating the counter and taking a maximum is simpler than sorting, and avoids the need to scan the whole value range.

💻 Benchmark Python3 Implementation

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        from collections import Counter
        res = -1
        for v, c in Counter(arr).items():
            if v == c:                     # value equals frequency
                res = max(res, v)
        return res


# Counting-array variant, O(n + V) with V = 500
class Solution2:
    def findLucky(self, arr: List[int]) -> int:
        cnt = [0] * 501
        for x in arr:
            cnt[x] += 1
        for v in range(500, 0, -1):        # descending -> first hit is the largest
            if cnt[v] == v:
                return v
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for the hash-map version (with O(k) iteration over distinct values), or O(n + V) for the counting-array version.
💾 Space Complexity
O(k) for the map, or O(V) = O(500) for the counting array, which is O(1) in terms of input size.

⚠️ Interview Pitfalls & Follow-ups

  • Returning 0 when nothing qualifies: the answer must be -1, and 0 can never be lucky since values start at 1.
  • Sorting and scanning for runs: works but O(n log n) and more error-prone than counting.
  • Confusing value with frequency: the condition is value == frequency, not frequency == 1.
  • Scanning the counting array ascending and returning the first hit: that yields the smallest lucky integer; scan descending for the largest.