1394. Find Lucky Integer in an Array - Explanation

Description

You are given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value.

Return the largest lucky integer in the array. If there is no lucky integer return -1.

Example 1:

Input: arr = [1,2,2,3,3,3]

Output: 3

Explanation: 1, 2 and 3 are all lucky numbers, 3 is the largest.

Example 2:

Input: arr = [2,2,2,3,3]

Output: -1

Constraints:

1 <= arr.length <= 500
1 <= arr[i] <= 500

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

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

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

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

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

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)$