Prerequisites
Before attempting this problem, you should be comfortable with:
- Hash Map - Used to count the frequency of each element in a single pass
- Array Traversal - Understanding how to iterate through arrays and track maximum values
- Frequency Counting - Concept of counting occurrences and comparing counts to values
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
numin the array:- Count how many times
numappears by scanning the entire array. - If the count equals
num, updateresto the maximum ofresandnum.
- Count how many times
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity:
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.
Time & Space Complexity
- Time complexity:
- Space complexity: or 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
resto the maximum ofresandnum.
- If the number equals its frequency, update
- Return
res.
Time & Space Complexity
- Time complexity:
- Space complexity:
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
numis within bounds, decrementarr[num - 1](making it negative if needed) to track frequency. - Follow the chain until we loop back or go out of bounds.
- Get the current number
- 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
-1if 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 -1Time & Space Complexity
- Time complexity:
- Space complexity:
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, returni + 1(this is the largest lucky integer). - If no match is found, return
-1.
Time & Space Complexity
- Time complexity:
- Space complexity:
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.