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.

1
2
3
4
5
6
7
8

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

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:

1
2
3
4
5

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

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.

1
2
3
4
5
6
7
8
9
10
11

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

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:

1
2
3
4
5
6
7
8

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 

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