Jobs

Interviews

Discussions

Find Lucky Integer in an Array

Easy

Microsoft

1 view

Topics:

Arrays

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:

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.

Constraints:

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

Try coding it in LeetCode

Find Lucky Integer in an Array

Easy

Microsoft

1 view

Topics:

Arrays

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:

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.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible integer values within the input array?
Can the input array be empty or null?
If there are multiple lucky integers, should I return the largest one, or is any lucky integer acceptable?
Is the input array sorted, or can it be in any arbitrary order?
What should I return if the array contains a value larger than the array's length?

Brute Force Solution

Approach

The brute force method for finding a lucky integer is to examine each number and count how often it appears in the group. We then check if any number's count matches the number itself.

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Go through the entire group and count how many times that number shows up.
Check if the number we started with is equal to the count we just found.
If they are equal, we've found a lucky number and remember it as a candidate.
Repeat this process for every number in the group.
If we find multiple lucky numbers, select the largest one.
If we don't find any lucky numbers, indicate that there isn't one.

Code Implementation

def find_lucky_integer(numbers):
    largest_lucky_integer = -1

    for current_number in numbers:
        number_count = 0
        
        for number in numbers:
            if number == current_number:
                number_count += 1

        # Check if the number's frequency equals the number itself
        if current_number == number_count:

            #We only want to consider it lucky if it is
            if current_number > largest_lucky_integer:
                largest_lucky_integer = current_number

    #Return -1 if no lucky number is found
    return largest_lucky_integer

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n elements in the array. For each element, it iterates through the entire array again to count its occurrences. Therefore, for each of the n elements, we perform approximately n operations. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(1) – The brute force method iterates through the array, keeping track of a 'count' variable and potentially a 'largest lucky number' variable. These variables consume constant space regardless of the input array size, N. No additional data structures like arrays, hash maps, or sets are created to store intermediate results or counts. Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the lucky number is to first count how many times each number appears in the list. Then, we simply check if any number's count matches the number itself, prioritizing the largest such number.

Here's how the algorithm would work step-by-step:

First, create a system to count how many times each number appears in the list.
Once you have these counts, go through each unique number in descending order.
For each number, check if its count is the same as the number itself. If it is, then you've found the lucky number.
If you find a lucky number, immediately return it. Otherwise if you check all numbers and there are no lucky numbers return -1.

Code Implementation

def find_lucky_integer(integers: list[int]) -> int:
    number_counts = {}

    for number in integers:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    # Iterate through unique numbers in descending order.
    for number in sorted(number_counts.keys(), reverse=True):

        # Check if the count matches the number itself
        if number_counts[number] == number:

            return number

    # If no lucky integer is found, return -1.
    return -1

Big(O) Analysis

Time Complexity

O(n) – The first step involves counting the frequency of each number, which requires iterating through the input array of size n once, taking O(n) time. The second step iterates through the unique numbers (at most n) in descending order to check if the count matches the number itself. This iteration also takes O(n) time in the worst case. Because these steps occur in sequence, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a counting system (likely a hash map or an array) to store the frequency of each number in the input list. In the worst case, all numbers in the input list are unique, requiring storage for N counts, where N is the number of elements in the input array. The auxiliary space used is thus proportional to the number of unique elements in the input array, which can be at most N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as there are no elements to process.
Array with a single element	Check if the single element's value is equal to 1, returning the element or -1 respectively.
Array with all identical values (e.g., [2, 2, 2])	The frequency will equal the value in this case, so return the value if it's the only one; otherwise, find the largest lucky number.
Array with no lucky integers	After processing the array, if no lucky integer is found, return -1.
Array with multiple lucky integers	The algorithm should correctly identify all lucky integers and return the largest among them.
Large array size (performance considerations)	Use a hash map (dictionary) to efficiently count frequencies instead of nested loops for better time complexity.
Array containing zero values	The algorithm should correctly handle zero values, which will never be considered lucky since the frequency cannot be zero unless the array is empty.
Array containing large positive integers close to integer limit	Ensure that the frequency counting and comparison logic does not cause integer overflow issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible integer values within the input array?
Can the input array be empty or null?
If there are multiple lucky integers, should I return the largest one, or is any lucky integer acceptable?
Is the input array sorted, or can it be in any arbitrary order?
What should I return if the array contains a value larger than the array's length?

Brute Force Solution

Approach

The brute force method for finding a lucky integer is to examine each number and count how often it appears in the group. We then check if any number's count matches the number itself.

Here's how the algorithm would work step-by-step:

Take the first number in the group.
Go through the entire group and count how many times that number shows up.
Check if the number we started with is equal to the count we just found.
If they are equal, we've found a lucky number and remember it as a candidate.
Repeat this process for every number in the group.
If we find multiple lucky numbers, select the largest one.
If we don't find any lucky numbers, indicate that there isn't one.

Code Implementation

def find_lucky_integer(numbers):
    largest_lucky_integer = -1

    for current_number in numbers:
        number_count = 0
        
        for number in numbers:
            if number == current_number:
                number_count += 1

        # Check if the number's frequency equals the number itself
        if current_number == number_count:

            #We only want to consider it lucky if it is
            if current_number > largest_lucky_integer:
                largest_lucky_integer = current_number

    #Return -1 if no lucky number is found
    return largest_lucky_integer

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a system to count how many times each number appears in the list.
Once you have these counts, go through each unique number in descending order.
For each number, check if its count is the same as the number itself. If it is, then you've found the lucky number.
If you find a lucky number, immediately return it. Otherwise if you check all numbers and there are no lucky numbers return -1.

Code Implementation

def find_lucky_integer(integers: list[int]) -> int:
    number_counts = {}

    for number in integers:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    # Iterate through unique numbers in descending order.
    for number in sorted(number_counts.keys(), reverse=True):

        # Check if the count matches the number itself
        if number_counts[number] == number:

            return number

    # If no lucky integer is found, return -1.
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return -1 immediately as there are no elements to process.
Array with a single element	Check if the single element's value is equal to 1, returning the element or -1 respectively.
Array with all identical values (e.g., [2, 2, 2])	The frequency will equal the value in this case, so return the value if it's the only one; otherwise, find the largest lucky number.
Array with no lucky integers	After processing the array, if no lucky integer is found, return -1.
Array with multiple lucky integers	The algorithm should correctly identify all lucky integers and return the largest among them.
Large array size (performance considerations)	Use a hash map (dictionary) to efficiently count frequencies instead of nested loops for better time complexity.
Array containing zero values	The algorithm should correctly handle zero values, which will never be considered lucky since the frequency cannot be zero unless the array is empty.
Array containing large positive integers close to integer limit	Ensure that the frequency counting and comparison logic does not cause integer overflow issues.