Teaching Kids Programming – Finding the Largest Lucky Number in the Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

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

Example 2:
Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

Example 4:
Input: arr = [5]
Output: -1

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

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

Hints:
Count the frequency of each integer in the array.
Get all lucky numbers and return the largest of them.

Algorithm Find Largest Lucky Number

A mode is the number appears most. In this case, we need to find numbers whose frequencies are the same as the values. We can use the Counter to do this.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        c = Counter(arr)
        x = []
        for i in c:
            if i == c[i]:
                x.append(i)
        return max(x) if x else -1

Two liners using Python:

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        c = Counter(arr)
        x = [i for i in c if i == c[i]]
        return max(x) if x else -1

The above algorithm takes O(N) time and O(N) space via a dictionary (hash table).

We can also do this via sorting – which takes O(NLogN) time. The numbers are sorted from largest to smallest, and we keep a counter for the current streak. If the current number does not equal to next one, we check if it is a lucky number and return if it is. Otherwise we reset the streak.

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        arr.sort(reverse=True)
        c = 0
        for i in range(len(arr)):
            c += 1
            if i == len(arr) - 1 or arr[i] != arr[i + 1]:
                if arr[i] == c:
                    return c
                c = 0
        return -1

We can also do this via bruteforce. Use count function to count the elements on the fly. This takes O(N^2) time:

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        ans = -1
        for num in arr:
            n = arr.count(num)
            if num == n and num > ans:
                ans = num
        return ans 

See also: Finding the Lucky Numbers in a Matrix

–EOF (The Ultimate Computing & Technology Blog) —