1394. Find Lucky Integer in an Array

EasyArrayHash TableCounting

Problem Description

In this problem, we are given an array of integers called arr. We need to find an integer that is considered "lucky". A lucky integer is defined as an integer that occurs in the array with a frequency equal to its value. In other words, if we pick a number from the array, that number is lucky if it appears on the list exactly that many times. Our task is to return the largest such lucky integer found in the array. If there is no integer that meets the criteria for being lucky, we should return -1.

To solve this, one can inspect every unique number in the array and check if its value equals the number of times it appears in the array. Then, the largest of these numbers that satisfy the condition will be our answer. If we do not find any number meeting the condition, our answer would default to -1.

Intuition

The intuition behind the solution is to use a hash map (dictionary in Python) to keep track of the frequencies of each unique integer in the given array. We do this using Counter, which is a specialized dictionary from Python's collections module, designed for counting hashable objects.

Once we have the frequency of each integer, we iterate through the items of this dictionary. Here we make two checks for each element x with frequency v:

If the value x equals its corresponding frequency v in the array (i.e., x is a lucky number).
If this lucky number is larger than any we have seen earlier.

If both conditions are true, we update our answer ans to the current number x. If, after checking all elements, we don't find any lucky number, ans remains -1, which is also our default answer.

This solution ensures that we consider the largest lucky integer because we keep updating ans every time we find a larger lucky integer. The final answer is the largest one found or -1 if no lucky integers are present.

Solution Approach

The implementation of the solution provided uses a Counter from Python's collections module which is a subclass of dictionary that is designed to efficiently count the frequency of items.

Here is the step-by-step explanation of the implementation:

We first create a Counter for the input array arr. The Counter collects the frequency of each integer value into a dictionary-like object, where keys are the integer values from the array, and their corresponding values are their respective counts (frequencies).
```
cnt = Counter(arr)
```
We initialize a variable ans with a value of -1. This will hold our largest lucky integer value or remain -1 if no lucky integers are found.
```
ans = -1
```
The next step is to iterate over the items in the Counter object. We use a for-loop that gets each item as a tuple x, v where x is the integer and v is its frequency in arr.
```
for x, v in cnt.items():
```
Inside the loop, we apply our logic to check if an integer is lucky. For an integer to be lucky, its value must be equal to its frequency (x == v). If this condition is true, we are also interested if it's larger than our current answer [ans < x].

If an integer satisfies both conditions, it becomes our new answer as it's a lucky number and it is greater than any lucky number found so far. This ensures that by the end of the iteration, ans will hold the highest lucky integer.
```
if x == v and ans < x:
    ans = x
```
After the iteration completes, we return the value stored in ans. This will either be the largest lucky integer in the array or -1 if no lucky integers were found.
```
return ans
```

The algorithm used in this solution has a time complexity of O(n), where n is the number of elements in the array. This is due to the fact that we pass through the array once to create the frequency counter, and we pass through the dictionary of unique values, which also requires O(n) in the worst case when all elements are unique.

One key point to underline here is the use of the Counter data structure, which is optimized for counting and can be far more efficient than manually implementing a frequency count, especially for large datasets. The use of this data structure greatly simplifies the code and reduces the opportunity for errors.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example where the given array arr is [2, 2, 3, 4, 4, 4, 4, 5, 5].

First, create a Counter object for the array which will count the frequencies of each integer. The Counter will look as follows:

cnt = Counter([2, 2, 3, 4, 4, 4, 4, 5, 5])
# Counter({4: 4, 2: 2, 5: 2, 3: 1})

Now initialize a variable ans with a value of -1 to hold the largest lucky integer.
```
ans = -1
```

Iterate over the items in the Counter. Each item returned by cnt.items() will be a key-value pair of the integer and its frequency. For example, the first pair would be (4, 4).

for x, v in cnt.items():
# loop iterations:
# (4, 4)
# (2, 2)
# (5, 2)
# (3, 1)

Inside the loop, check if an integer is lucky (i.e., its value is equal to its frequency). For example, when x is 4 and v is 4, check x == v. Since 4 is equal to its frequency, check if it is larger than ans. As ans is -1, update ans = 4.

Continue the loop and find that 2 is also lucky since its value matches its frequency. However, 2 is not larger than the current ans which is 4, so no update is made. Similarly, 5 and 3 are not lucky integers because their values do not match their frequencies.
Upon completion of the loop, return the value of ans. Since 4 was the largest lucky integer found, ans = 4 will be returned.

Therefore, in this example, the largest lucky integer is 4, and that is the value that our algorithm would accurately return for the given array.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def findLucky(self, arr: List[int]) -> int:
5        # Create a counter to count the occurrences of each number in the array
6        number_counter = Counter(arr)
7      
8        # Initialize the answer to -1, as -1 would be the default return value if no lucky integer is found
9        lucky_integer = -1
10      
11        # Iterate through the items in the counter
12        for number, count in number_counter.items():
13            # A lucky integer is defined as an integer whose value is equal to the number of times it appears in the array
14            if number == count and lucky_integer < number:
15                # Update the lucky integer to the current number if it's greater than current lucky_integer
16                lucky_integer = number
17      
18        # Return the largest lucky integer found, or -1 if none found
19        return lucky_integer
20

1class Solution {
2    // This method finds the lucky number in an array. A lucky number is defined as
3    // a number that has a frequency in the array equal to its value.
4    public int findLucky(int[] arr) {
5        // Create an array to store the frequency of each number. Assuming the maximum
6        // number value is 500, thus the length is 510 to include zero-indexing padding.
7        int[] frequency = new int[510];
8      
9        // Iterate through the input array and increment the frequency count for each number.
10        for (int num : arr) {
11            // Increment the frequency for the number found in the array.
12            ++frequency[num]; // Correct the loop to iterate over the 'arr' elements.
13        }
14      
15        // Initialize the lucky number to -1, as a default value if there's no lucky number.
16        int luckyNumber = -1;
17      
18        // Iterate through the frequency array to find a lucky number starting from 1
19        // since the problem statement implies lucky numbers are positive.
20        for (int i = 1; i < frequency.length; ++i) {
21            // If the frequency of a number is the same as its value, update the luckyNumber.
22            if (frequency[i] == i) {
23                luckyNumber = i; // A bigger number will always override previous one, if found.
24            }
25        }
26      
27        // Return the lucky number, which will be -1 if none was found.
28        return luckyNumber;
29    }
30}
31

1#include <vector>
2#include <algorithm> // for fill_n
3
4class Solution {
5public:
6    /**
7     * Find the largest lucky number in the array.
8     * A lucky number is defined as a number which has a frequency in the array equal to its value.
9     * @param arr the input vector of integers
10     * @return the largest lucky number or -1 if no such number exists
11     */
12    int findLucky(vector<int>& arr) {
13        // Create an array to store counts of each number, initial size is enough for constraints
14        int count[510];
15        // Initialize all elements of count array to 0
16        fill_n(count, 510, 0);
17
18        // Iterate through the input array and increment the corresponding count index
19        for (int num : arr) {
20            ++count[num];
21        }
22
23        // Initialize the answer as -1, which means no lucky number found
24        int ans = -1;
25        // Loop through the count array to find the largest lucky number
26        for (int i = 1; i < 510; ++i) {
27            if (count[i] == i) {
28                ans = i; // Update the answer if a new lucky number is found
29            }
30        }
31
32        // Return the largest lucky number or -1 if none were found
33        return ans;
34    }
35};
36

1function findLucky(arr: number[]): number {
2    // Create an array to count the frequencies of each number, large enough to hold all potential values.
3    const frequencyCounter = new Array(510).fill(0);
4
5    // Iterate through the array and increment the count of each number in the frequencyCounter.
6    for (const number of arr) {
7        frequencyCounter[number]++;
8    }
9
10    // Initialize the lucky number to -1, indicating that no lucky number has been found yet.
11    let luckyNumber = -1;
12
13    // Iterate through the frequencyCounter, starting from 1 since 0 can't be a lucky number.
14    for (let i = 1; i < frequencyCounter.length; ++i) {
15        // Check if the current number's count is the same as the number itself.
16        if (frequencyCounter[i] === i) {
17            // Update the lucky number since a new lucky number is found.
18            // As we iterate from low to high, this will ensure the largest lucky number will be recorded last.
19            luckyNumber = i;
20        }
21    }
22
23    // Return the lucky number, which is -1 if none was found or the largest lucky number from the array.
24    return luckyNumber;
25}
26

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed as follows:

Counting the frequencies of elements in arr using Counter(arr) – This operation runs in O(n) time where n is the length of arr, as it requires a single pass over all the elements.
Iterating over the items in the cnt dictionary to find the lucky integer – The iteration over the dictionary items will take at most O(n) time since there can't be more unique elements than the number of elements in arr.

As a result, the overall time complexity is O(n) + O(n) = O(2n) which simplifies to O(n).

Space Complexity

The space complexity of the provided code can be considered in the following parts:

The space used by the Counter to store the frequency of each element – This takes up O(u) space where u is the number of unique elements in arr, which in the worst case can be up to n.
The space used for the variable ans – This is constant space, O(1).

Thus, the overall space complexity is O(u) + O(1) which simplifies to O(u). When considering the worst case where all elements are unique, this becomes O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know