algoadvance

Given an array of integers arr, a lucky integer is an integer which 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:

Input: arr = [2,2,3,4]
Output: 2
Explanation: The frequency of 2 is 2.

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

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

Input: arr = [7,7,7,7,7,7,7]
Output: 7

Clarifying Questions

  1. Can the array contain negative numbers?
    • According to the problem statement and examples provided, it does not specify allowing negative numbers, so we will assume it only contains non-negative integers.
  2. What is the length range of the array?
    • The problem does not specify the constraints on the size of the array. However, for the purpose of this problem, we can assume it fits within standard array size limits for algorithms (e.g., up to 10^5 elements).
  3. Do we need to handle edge cases like an empty array?
    • If the array does not contain any numbers, we should return -1 as there won’t be any integers to evaluate.

Strategy

  1. Frequency Count: Use a dictionary or collections.Counter to count the frequencies of each number in the array.
  2. Filter Lucky Integers: Iterate through the frequency dictionary and collect integers whose frequency matches their value.
  3. Find Maximum: Find the maximum value from the collected lucky integers.
  4. Return the Result: If no lucky integers exist, return -1.

Code

from collections import Counter

def findLucky(arr):
    freq = Counter(arr)
    lucky_integers = [num for num, count in freq.items() if num == count]
    return max(lucky_integers, default=-1)

# Example Usages
print(findLucky([2, 2, 3, 4]))  # Output: 2
print(findLucky([1, 2, 2, 3, 3, 3]))  # Output: 3
print(findLucky([2, 2, 2, 3, 3]))  # Output: -1
print(findLucky([5]))  # Output: -1
print(findLucky([7, 7, 7, 7, 7, 7, 7]))  # Output: 7

Time Complexity

  1. Frequency Count: Counting the frequency of elements using Counter takes O(n) time, where n is the number of elements in the array.
  2. Filtering Lucky Integers: This takes O(k) time where k is the number of unique elements which in the worst case is O(n).
  3. Finding Maximum: Finding the maximum in the list of lucky integers takes O(m) where m is the number of lucky integers. In the worst case, m is also O(n).

Thus, the overall time complexity is:

Try our interview co-pilot at AlgoAdvance.com