Description

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

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

Example 2:

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

Example 3:

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

Constraints:

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

Solution

Brute Force

In brute force approach, you would iterate through each element of the array arr and verify the frequency of this number in the arr. If it’s same, modify the largestLuckyNumber variable with the biggest value seen so far.

 1class Solution {
 2    public int findLucky (int[] arr) {
 3        int largestLuckyNumber = -1;
 4        for (int i = 0; i < arr.length; i++) {
 5            int count = 0;
 6            for (int j = 0; j < arr.length; j++) {
 7                if (arr[i] == arr[j])
 8                    count++;
 9            }
10            if (count == arr[i]){
11                largestLuckyNumber = Math.max(largestLuckyNumber, arr[i]);
12            }
13        }
14        return largestLuckyNumber;
15    }
16}
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

Using Sorting

Another approach to solve this problem would to to sort the array in ascending order. This way we will have the largest number towards the right end of the arr. So, we can start iterating from the right and at each iteration, we make sure if it’s same value as the next value and increment the currentCount to keep track of how many times current value is occurring. When the values don’t match, that means we have found the occurrences of this value. At this point, we check if the currentCount is same as the value we were tracking. If yes, simply return because this will be the largest value in the arr else continue with the next value on the left.

 1class Solution {
 2    public int findLucky (int[] arr) {
 3        Arrays.sort(arr);
 4        int currentCount = 0;
 5        for (int i = arr.length - 1; i >= 0; i--) {
 6            currentCount++;
 7            if (i == 0 || arr[i] != arr[i - 1]) {
 8                if (currentCount == arr[i])
 9                    return currentCount;
10                currentCount = 0;
11            }
12        }
13        return -1;
14    }
15}
  • Time Complexity: O(n log n) because of sorting operation
  • Space Complexity: O(1) to O(n) depending on the sorting algorithm used which may require additional space to sort elements.

Using Array

We could also use array to track the frequency of each element. This way we have to make first pass to insert the frequency into new array counts. Again we have to create array of size upto maximum possible value in arr input array which is 500 and we need one additional element. Now, the problem has a constraint that the number will be greater than or equal to 1. This means we have to ignore index position 0 otherwise, we may always end up returning 0 as the result if no lucky number found. Because 0 can never occur, it will always have frequency of 0 which is same as definition of lucky number in our problem. This solution requires space for storing frequency of each of 500 elements which may be a waste if we have only few elements in arr because we might end up having most of the values of counts array as zero.

 1class Solution {
 2    public int findLucky (int[] arr) {
 3        int[] counts = new int[501];
 4
 5        for (int i = 0; i < arr.length; i++) {
 6            counts[arr[i]]++;
 7        }
 8
 9        for (int i = counts.length - 1; i >= 1; i--) { // count[0] is always 0, so ignore that
10            if (counts[i] == i)
11                return i;
12        }
13        return -1;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: O(n) because we will have to store n + 1 values in counts array.

Using HashMap

We could also use HashMap to track frequency of each number in input array arr. Again, we have to make two pass. First to insert the frequency into frequencyMap and next iteration to find the largest lucky number from the frequencyMap.

 1class Solution {
 2    public int findLucky (int[] arr) {
 3        Map<Integer, Integer> frequency = new HashMap<>();
 4        int largestLuckyNumber = -1;
 5        for (int num : arr) {
 6            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
 7        }
 8        for (Map.Entry<Integer, Integer> entry: frequency.entrySet()) {
 9            if (entry.getKey() == entry.getValue()) {
10                largestLuckyNumber = Math.max(largestLuckyNumber, entry.getKey());
11            }
12        }
13        return largestLuckyNumber;
14    }
15}
  • Time Complexity: O(n)
  • Space Complexity: O(n) in worst case we may have up to n unique numbers.