Find Lucky Integer in an Array - Practice Coding Problems

Find Lucky Integer in an Array - Problem

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.

Input & Output

Example 1 — Basic Lucky Number

$ Input: arr = [2,2,3,4]

› Output: 2

💡 Note: Number 2 appears 2 times, so 2 is lucky. Number 3 appears 1 time (3 ≠ 1), number 4 appears 1 time (4 ≠ 1). Only 2 is lucky.

Example 2 — No Lucky Numbers

$ Input: arr = [1,2,2,3,3,3]

› Output: -1

💡 Note: Number 1 appears 1 time (1 = 1, lucky), number 2 appears 2 times (2 = 2, lucky), number 3 appears 3 times (3 = 3, lucky). The largest lucky number is 3. Wait, let me recalculate: 1→1 time (lucky), 2→2 times (lucky), 3→3 times (lucky). Largest is 3.

Example 3 — Multiple Lucky Numbers

$ Input: arr = [7,7,7,7,7,7,7]

› Output: 7

💡 Note: Number 7 appears 7 times, so 7 is lucky. This is the only number and it's lucky.

Constraints

1 ≤ arr.length ≤ 500
1 ≤ arr[i] ≤ 500

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array with integers, need to find numbers equal to their frequency

Count Frequencies

Use hash map to count how many times each number appears

Find Lucky Numbers

Check which numbers have frequency equal to their value

Key Takeaway

🎯 Key Insight: A number is lucky when its frequency in the array equals its value - use hash map counting to find them efficiently

Asked in

a Amazon 25 G Google 20 M Microsoft 15

The key insight is to count the frequency of each number and check if any number equals its frequency count. The optimal approach uses a hash map to count frequencies in O(n) time, then finds the largest number where value equals frequency. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Single-Pass with Early Maximum	O(n)	O(n)	Count frequencies and track maximum lucky number in a single pass
Brute Force Counting	O(n²)	O(1)	Count frequency of each number by scanning the array multiple times
Two-Pass Hash Map	O(n)	O(n)	First pass builds frequency map, second pass finds largest lucky number

Single-Pass with Early Maximum — Algorithm Steps

Initialize frequency map and max lucky tracker
For each number, update its frequency
After updating frequency, check if it becomes lucky
Update maximum lucky number if needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Each Number

Update frequency and immediately check if lucky

Track Maximum

Keep track of the largest lucky number found so far

Final Result

Return maximum lucky number after single pass

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 1000

typedef struct {
    int num;
    int count;
} FreqEntry;

int solution(int* arr, int size) {
    FreqEntry freq[MAX_SIZE];
    int freqSize = 0;
    int maxLucky = -1;
    
    for (int i = 0; i < size; i++) {
        int num = arr[i];
        int found = 0;
        
        // Update frequency
        for (int j = 0; j < freqSize; j++) {
            if (freq[j].num == num) {
                freq[j].count++;
                
                // Check if now lucky
                if (freq[j].count == num) {
                    if (maxLucky == -1 || num > maxLucky) {
                        maxLucky = num;
                    }
                }
                found = 1;
                break;
            }
        }
        
        // Add new number
        if (!found) {
            freq[freqSize].num = num;
            freq[freqSize].count = 1;
            
            // Check if immediately lucky
            if (num == 1) {
                if (maxLucky == -1 || num > maxLucky) {
                    maxLucky = num;
                }
            }
            freqSize++;
        }
    }
    
    return maxLucky;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[MAX_SIZE];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(arr, size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array, each hash map operation is O(1)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n unique numbers with their frequencies

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single-Pass with Early Maximum — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler