Find Lucky Integer in an Array

How it works

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.

Steps

1. 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.
2. Traverse the array from right to left.
3. For each index i, extract the count by right-shifting by 10 bits.
4. If the count equals i + 1, return i + 1 (this is the largest lucky integer).
5. If no match is found, return -1.

Complexity

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

Things to watch for

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.

from typing import List

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

class Solution {
public:
    int findLucky(vector<int>& arr) {
        for (int num : arr) {
            int idx = num & ((1 << 10) - 1);
            if (idx <= arr.size()) {
                arr[idx - 1] += (1 << 10);
            }
        }

        for (int i = arr.size() - 1; i >= 0; i--) {
            int cnt = arr[i] >> 10;
            if (cnt == i + 1) return i + 1;
        }
        return -1;
    }
};