Solutions

1. Brute Force

Intuition

A lucky integer is one whose value equals its frequency in the array. The simplest approach is to check each number by counting how many times it appears. If the count matches the number itself, it's a lucky integer. We track the largest one found.

Algorithm

Initialize res = -1 (no lucky integer found yet).
For each number num in the array:
- Count how many times num appears by scanning the entire array.
- If the count equals num, update res to the maximum of res and num.
Return res.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        res = -1

        for num in arr:
            cnt = 0
            for a in arr:
                if num == a:
                    cnt += 1
            if cnt == num:
                res = max(res, num)

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Sorting

Intuition

After sorting, identical numbers are grouped together. By traversing from right to left, we can count consecutive occurrences of each number. The first lucky integer we find (scanning from largest to smallest) is guaranteed to be the largest.

Algorithm

Sort the array.
Traverse from right to left, counting consecutive equal elements (the streak).
When the current element differs from the previous one (or we reach the start):
- Check if the streak count equals the element value.
- If so, return that element immediately (it's the largest lucky integer).
- Reset the streak counter.
If no lucky integer is found, return -1.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        arr.sort()
        streak = 0
        for i in range(len(arr) - 1, -1, -1):
            streak += 1
            if i == 0 or (arr[i] != arr[i - 1]):
                if arr[i] == streak:
                    return arr[i]
                streak = 0
        return -1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Hash Map

Intuition

We can count the frequency of each number in one pass using a hash map. Then we iterate through the map to find numbers where the key equals its value (frequency). This avoids repeated counting and is more efficient than brute force.

Algorithm

Build a frequency map by iterating through the array once.
Initialize res = -1.
For each (number, frequency) pair in the map:
- If the number equals its frequency, update res to the maximum of res and num.
Return res.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        res = -1

        for num in cnt:
            if num == cnt[num]:
                res = max(num, res)
        
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Negative Marking

Intuition

If we can modify the input array, we can use it as a frequency counter without extra space. For a number num, we use index num - 1 to store its frequency by making that position negative and decrementing it. After processing, a position i with value -x means the number i + 1 appeared x times.

Algorithm

For each position i, follow the chain of values to increment counts:
- Get the current number num.
- If num is within bounds, decrement arr[num - 1] (making it negative if needed) to track frequency.
- Follow the chain until we loop back or go out of bounds.
Traverse from the end of the array backward.
For each index i, check if -arr[i] == i + 1 (frequency equals the number).
Return the first match found, or -1 if none exists.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        n = len(arr)
        for i in range(n):
            prev, num = i, arr[i]
            while 0 < num <= n:
                nxt = arr[num - 1]
                arr[num - 1] = min(0, arr[num - 1]) - 1
                if num - 1 <= i or num - 1 == prev:
                    break
                prev = num - 1
                num = nxt
        
        for i in range(n - 1, -1, -1):
            if -arr[i] == i + 1:
                return i + 1
        
        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

5. Bit Manipulation

Intuition

We can use bit manipulation to store both the original value and the frequency count in the same array element. Since values are at most 500, they fit in 10 bits. We use the lower 10 bits for the original value and the upper bits for the count. This allows in-place frequency tracking.

Algorithm

For each number in the array:
- Extract the original value using a bitmask (lower 10 bits).
- If the value is within the array bounds, increment the count at that index by adding 1 << 10.
Traverse the array from right to left.
For each index i, extract the count by right-shifting by 10 bits.
If the count equals i + 1, return i + 1 (this is the largest lucky integer).
If no match is found, return -1.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        for num in arr:
            idx = num & ((1 << 10) - 1)
            if idx <= len(arr):
                arr[idx - 1] += (1 << 10)

        for i in range(len(arr) - 1, -1, -1):
            cnt = arr[i] >> 10
            if cnt == i + 1:
                return i + 1
        return -1

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Return -1 When No Lucky Integer Exists

A lucky integer only exists if a number's value equals its frequency. If no such number is found, the function must return -1. Forgetting to initialize the result to -1 or failing to handle the case where no lucky integer exists will produce incorrect output for inputs like [1, 1] where no number satisfies the condition.

Not Tracking the Maximum Lucky Integer

When multiple lucky integers exist in the array, you must return the largest one. Simply returning the first lucky integer found without comparing it to previously found ones produces wrong results. Always use max(result, num) when a lucky integer is found, or iterate from largest to smallest and return immediately upon finding one.