Find Lucky Integer in an Array

Difficulty: Easy | Acceptance: 75.50% | Paid: No Topics: Array, Hash Table, Counting

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

Return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

• Examples
• Constraints
• Approach 1: Hash Map Frequency Count
• Approach 2: Sorting
• Approach 3: Counting Array

Examples

Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest one which is 3.

Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.

Constraints

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

Approach 1: Hash Map Frequency Count

Intuition We can iterate through the array to count the frequency of each number using a hash map. Then, we iterate through the map entries to find numbers where the key equals the value, keeping track of the maximum such number.

Steps

• Initialize an empty hash map.
• Iterate through the input array arr, incrementing the count for each number in the map.
• Initialize a variable max_lucky to -1.
• Iterate through the entries in the map. If the key (number) equals the value (frequency), update max_lucky with the maximum of itself and the key.
• Return max_lucky.

class Solution:
    def findLucky(self, arr: list[int]) -> int:
        freq = {}
        for num in arr:
            freq[num] = freq.get(num, 0) + 1
        
        max_lucky = -1
        for num, count in freq.items():
            if num == count:
                max_lucky = max(max_lucky, num)
        
        return max_lucky

Complexity

• Time: O(n), where n is the number of elements in the array. We iterate through the array once to build the map and once through the map (which has at most n elements).
• Space: O(n), to store the frequency map in the worst case where all elements are distinct.
• Notes: This is a standard approach for frequency counting problems.

Approach 2: Sorting

Intuition If we sort the array, identical numbers will be grouped together. We can then iterate through the sorted array, counting the size of each group. If the group size equals the number itself, it is a lucky integer. Since we process numbers in increasing order, the last lucky integer found will be the largest.

Steps

• Sort the array in non-decreasing order.
• Initialize max_lucky to -1 and i to 0.
• While i is less than the length of the array:
  • Store the current number curr = arr[i].
  • Initialize count to 0.
  • While i is within bounds and arr[i] == curr, increment count and i.
  • If count == curr, update max_lucky = curr.
• Return max_lucky.

class Solution:
    def findLucky(self, arr: list[int]) -> int:
        arr.sort()
        n = len(arr)
        i = 0
        max_lucky = -1
        
        while i < n:
            curr = arr[i]
            count = 0
            while i < n and arr[i] == curr:
                count += 1
                i += 1
            
            if count == curr:
                max_lucky = curr
                
        return max_lucky

Complexity

• Time: O(n log n) due to the sorting step.
• Space: O(1) or O(n) depending on the sorting algorithm’s space complexity (e.g., heapsort uses O(1), merge sort uses O(n)).
• Notes: Modifies the input array. Less efficient than the hash map approach for time complexity.

Approach 3: Counting Array

Intuition The constraints state that 1 <= arr[i] <= 500. This small range allows us to use a fixed-size array (counting sort style) instead of a hash map. We can count frequencies in an array of size 501. Then, we iterate backwards from 500 down to 1. The first number we find where count[i] == i is the largest lucky integer.

Steps

• Initialize an integer array count of size 501 with all zeros.
• Iterate through arr, incrementing count[num] for each number.
• Iterate from i = 500 down to i = 1:
  • If count[i] == i, return i.
• If the loop finishes without returning, return -1.

class Solution:
    def findLucky(self, arr: list[int]) -> int:
        count = [0] * 501
        for num in arr:
            count[num] += 1
        
        for i in range(500, 0, -1):
            if count[i] == i:
                return i
        
        return -1

Complexity

• Time: O(n), where n is the length of the array. We iterate once to count and once through the fixed 501 size array.
• Space: O(1), since the count array size is fixed (501) regardless of input size.
• Notes: This is the most optimal approach for this specific problem due to the constraints.