Find the Largest Lucky Number

mediumSave

ArrayCountingHash Table

Given an array of integers arr, a lucky number is an integer whose frequency in the array is equal to its value. Your task is to find the largest lucky number in the array. If there are multiple lucky numbers, return the largest one. If no lucky number exists, return -1.

Example 1

Input

[
  "[[2,2,3,4]]"
]

Output

Explanation. The number 2 appears 2 times, which is equal to its value. No other number is lucky.

Example 2

Input

[
  "[[1,2,2,3,3,3]]"
]

Output

Explanation. 1 appears 1 time (lucky). 2 appears 2 times (lucky). 3 appears 3 times (lucky). The largest among these is 3.

Example 3

Input

[
  "[[4,3,2,1]]"
]

Output

-1

Explanation. No number's frequency matches its value. For example, 4 appears 1 time (not 4 times).

Example 4

Input

[
  "[[7,7,7,7,7,7,7]]"
]

Output

Explanation. The number 7 appears 7 times, which is equal to its value. It is the only lucky number.

Example 5

Input

[
  "[[5,5,5,5,5,1,2,3]]"
]

Output

Explanation. The number 5 appears 5 times (lucky). Numbers 1, 2, 3 appear once, but their values are not 1, 2, or 3 respectively, so they are not lucky. The largest lucky number is 5.

Example 6

Input

[
  "[[1]]"
]

Output

Explanation. The number 1 appears 1 time, which is equal to its value. It is the only lucky number.

Example 7

Input

[
  "[[5]]"
]

Output

-1

Explanation. The number 5 appears 1 time, which is not equal to its value (5). No lucky number exists.

Example 8

Input

[
  "[[2,2,3,3,3,4,4,4,4,1]]"
]

Output

Explanation. 1 appears 1 time (lucky). 2 appears 2 times (lucky). 3 appears 3 times (lucky). 4 appears 4 times (lucky). The largest lucky number among them is 4.

Follow-up: Can you solve this problem with a time complexity better than O(N log N) (e.g., if sorting is used) and optimal space complexity?

Constraints:

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

Views: 4