Find Lucky Integer in an Array solution and explanation
Google
9 more videos on this problem
LeetCode 1394 | Find Lucky Integer in an Array | Day 20 | 100 Days_LeetCode_Challenge|DSAwithedSlashedSlash · 10:05 · 8K views
Find Lucky Integer in an Array | Leetcode 1394Technosage · 11:18 · 4K views
1394. Find Lucky Integer in an Array LeetcodeCity Coder · 3:51 · 2K views
LeetCode 1394 Solution in Hindi | LeetCode Find Lucky Integer in an Array SolutionEngineering Digest · 4:47 · 2K views
Find Lucky Integer in an Array | Leetcode 1394 | Amazon Google Facebook interview questionSuper Lazy Coder · 7:39 · 1K views
1394. Find Lucky Integer in an Array || weekly-contest-182 || [C++ SOLUTION]code Explainer · 3:08 · 1K views
Find Lucky Integer in an Array | Leetcode #1394 | EasyMorning Byte · 3:33 · 865 views
1394. Find Lucky Integer in an Array | Leetcode Daily - PythonLeetcode Daily · 5:00 · 457 views
1394. Find Lucky Integer in an Array || In JAVA || Leetcode Problem || Easy #leetcodeQuick Learning With Sree · 5:13 · 385 views
LeetCode 1394 - Find Lucky Integer in an Array: A Microsoft JourneyThe Lofi Dev · 3:51 · 139 views
The 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.
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 <= 5001 <= arr[i] <= 500
Approach overview
Problem Overview: You are given an integer array arr. A number is called lucky if its value is equal to the number of times it appears in the array. Your task is to return the largest lucky integer. If no such number exists, return -1.
Approach 1: Using a Frequency Map (O(n) time, O(n) space)
Count how many times each number appears using a hash map. Iterate through the array once and update the frequency for each value. After building the map, iterate through the key-value pairs and check whether value == frequency. Track the maximum such value during the scan. Hash lookups and updates are constant time on average, making the overall complexity O(n). This approach works well for general cases and is the most common technique when solving frequency-based problems involving hash tables.
Approach 2: Using an Array to Track Frequencies (O(n) time, O(1) space)
The constraints limit values in arr to a small range, so you can replace the hash map with a counting array. Create a frequency array where the index represents the number and the value stores its count. Iterate through arr and increment the corresponding index. Then scan the frequency array and check which indices satisfy i == frequency[i], keeping the largest valid value. Since the array size is fixed by the constraint range, the extra space is effectively constant. This technique is a classic counting pattern frequently used in array problems.
Recommended for interviews: The frequency map approach is what most interviewers expect first. It demonstrates your ability to apply hash-based counting to reduce repeated scans. Mentioning the counting-array optimization shows deeper understanding of constraints and space tradeoffs, which signals stronger problem-solving skills.
Approach 1: Using a Frequency Map
This approach involves using a hash map (or dictionary) to store the frequency of each integer in the array. Once frequencies are calculated, iterate through the map to find integers whose value is equal to their frequency, and track the maximum of such values.
def findLucky(arr):
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
maxLucky = -1
for num, count in freq.items():
if num == count and num > maxLucky:
maxLucky = num
return maxLucky
arr = [1, 2, 2, 3, 3, 3]
print(findLucky(arr))import java.util.HashMap;
public class Main {
public static int findLucky(int[] arr) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int maxLucky = -1;
for (int num : freq.keySet()) {
if (num == freq.get(num) && num > maxLucky) {
maxLucky = num;
}
}
return maxLucky;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 3, 3};
System.out.println(findLucky(arr));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int findLucky(vector<int>& arr) {
unordered_map<int, int> freq;
for (int num : arr) {
freq[num]++;
}
int maxLucky = -1;
for (auto& [num, count] : freq) {
if (num == count && num > maxLucky) {
maxLucky = num;
}
}
return maxLucky;
}
int main() {
vector<int> arr = {1, 2, 2, 3, 3, 3};
cout << findLucky(arr) << endl;
return 0;
}function findLucky(arr) {
const freq = {};
for (let num of arr) {
freq[num] = (freq[num] || 0) + 1;
}
let maxLucky = -1;
for (let num in freq) {
if (Number(num) === freq[num] && Number(num) > maxLucky) {
maxLucky = Number(num);
}
}
return maxLucky;
}
const arr = [1, 2, 2, 3, 3, 3];
console.log(findLucky(arr));#include <stdio.h>
int findLucky(int* arr, int arrSize) {
int freq[501] = {0};
for (int i = 0; i < arrSize; i++) {
freq[arr[i]]++;
}
int maxLucky = -1;
for (int i = 1; i <= 500; i++) {
if (freq[i] == i) {
if (i > maxLucky) maxLucky = i;
}
}
return maxLucky;
}
int main() {
int arr[] = {1, 2, 2, 3, 3, 3};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", findLucky(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
public class Program {
public static int FindLucky(int[] arr) {
Dictionary<int, int> freq = new Dictionary<int, int>();
foreach (int num in arr) {
if (freq.ContainsKey(num)) {
freq[num]++;
} else {
freq[num] = 1;
}
}
int maxLucky = -1;
foreach (var kvp in freq) {
if (kvp.Key == kvp.Value && kvp.Key > maxLucky) {
maxLucky = kvp.Key;
}
}
return maxLucky;
}
public static void Main() {
int[] arr = { 1, 2, 2, 3, 3, 3 };
Console.WriteLine(FindLucky(arr));
}
}In this Python solution, a dictionary is used to store the frequency of each integer. We then iterate through this dictionary to find the largest lucky number.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the space required for the dictionary in the worst case.
Approach 2: Using an Array to Track Frequencies
This approach involves using an array to directly track the frequency of each integer. By using an array of fixed size, we can avoid using a hash map or dictionary, which optimizes space usage when the domain of the input elements is known.
def findLucky(arr):
freq = [0] * 501
for num in arr:
freq[num] += 1
maxLucky = -1
for i in range(1, 501):
if freq[i] == i and i > maxLucky:
maxLucky = i
return maxLucky
arr = [2, 2, 3, 4]
print(findLucky(arr))public class Main {
public static int findLucky(int[] arr) {
int[] freq = new int[501];
for (int num : arr) {
freq[num]++;
}
int maxLucky = -1;
for (int i = 1; i <= 500; i++) {
if (freq[i] == i && i > maxLucky) {
maxLucky = i;
}
}
return maxLucky;
}
public static void main(String[] args) {
int[] arr = {2, 2, 3, 4};
System.out.println(findLucky(arr));
}
}#include <iostream>
#include <vector>
using namespace std;
int findLucky(vector<int>& arr) {
int freq[501] = {0};
for (int num : arr) {
freq[num]++;
}
int maxLucky = -1;
for (int i = 1; i <= 500; i++) {
if (freq[i] == i && i > maxLucky) {
maxLucky = i;
}
}
return maxLucky;
}
int main() {
vector<int> arr = {2, 2, 3, 4};
cout << findLucky(arr) << endl;
return 0;
}function findLucky(arr) {
const freq = Array(501).fill(0);
for (let num of arr) {
freq[num]++;
}
let maxLucky = -1;
for (let i = 1; i <= 500; i++) {
if (freq[i] === i && i > maxLucky) {
maxLucky = i;
}
}
return maxLucky;
}
const arr = [2, 2, 3, 4];
console.log(findLucky(arr));#include <stdio.h>
int findLucky(int* arr, int arrSize) {
int freq[501] = {0};
for (int i = 0; i < arrSize; i++) {
freq[arr[i]]++;
}
int maxLucky = -1;
for (int i = 1; i <= 500; i++) {
if (freq[i] == i) {
if (i > maxLucky) maxLucky = i;
}
}
return maxLucky;
}
int main() {
int arr[] = {2, 2, 3, 4};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", findLucky(arr, arrSize));
return 0;
}using System;
public class Program {
public static int FindLucky(int[] arr) {
int[] freq = new int[501];
foreach (int num in arr) {
freq[num]++;
}
int maxLucky = -1;
for (int i = 1; i <= 500; i++) {
if (freq[i] == i && i > maxLucky) {
maxLucky = i;
}
}
return maxLucky;
}
public static void Main() {
int[] arr = { 2, 2, 3, 4 };
Console.WriteLine(FindLucky(arr));
}
}Using a pre-initialized array in Python, this solution computes frequencies without dictionaries. It ensures efficiency by exploiting the fixed range of input values.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1) because the auxiliary space is constant.
Approach 3: Counting
We can use a hash table or an array cnt to count the occurrences of each number in arr. Then, we iterate through cnt to find the largest x such that cnt[x] = x. If there is no such x, return -1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the arr.
function findLucky(arr: number[]): number {
const cnt: number[] = Array(501).fill(0);
for (const x of arr) {
++cnt[x];
}
for (let x = cnt.length - 1; x; --x) {
if (x === cnt[x]) {
return x;
}
}
return -1;
}func findLucky(arr []int) int {
cnt := [501]int{}
for _, x := range arr {
cnt[x]++
}
for x := len(cnt) - 1; x > 0; x-- {
if x == cnt[x] {
return x
}
}
return -1
}use std::collections::HashMap;
impl Solution {
pub fn find_lucky(arr: Vec<i32>) -> i32 {
let mut cnt = HashMap::new();
arr.iter().for_each(|&x| *cnt.entry(x).or_insert(0) += 1);
cnt.iter()
.filter(|(&x, &v)| x == v)
.map(|(&x, _)| x)
.max()
.unwrap_or(-1)
}
}class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function findLucky($arr) {
$cnt = array_fill(0, 501, 0);
foreach ($arr as $x) {
$cnt[$x]++;
}
for ($x = 500; $x > 0; $x--) {
if ($cnt[$x] === $x) {
return $x;
}
}
return -1;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Frequency Map | Time Complexity: O(n), where n is the length of the array. |
| Using an Array to Track Frequencies | Time Complexity: O(n), where n is the length of the array. |
| Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Map (Hash Table) | O(n) | O(n) | General case when counting occurrences of elements in an array |
| Counting Array (Frequency Array) | O(n) | O(1) | When the value range is small and known in advance |
Frequently asked questions
Is Find Lucky Integer in an Array easy or hard?
Find Lucky Integer in an Array is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly tests whether you recognize the frequency counting pattern and apply a hash map or counting array efficiently.
How to solve Find Lucky Integer in an Array in O(n)?
Traverse the array and maintain a frequency count using a hash map or counting array. After counting, iterate through the frequencies and check whether any number appears exactly the same number of times as its value. Track the maximum such number while scanning. This approach ensures linear O(n) time.
What is the best approach for Find Lucky Integer in an Array?
The most practical approach uses a hash map to count the frequency of each number. After building the frequency map in one pass, scan the entries and check which values satisfy value == frequency. This solution runs in O(n) time with O(n) space and is the method most interviewers expect.
What data structure is used in Find Lucky Integer in an Array?
The core data structure is a hash table used to store element frequencies. In cases where the value range is small, a counting array can replace the hash map for better space efficiency while maintaining O(n) time complexity.
What is the time complexity of Find Lucky Integer in an Array?
The optimal solution runs in O(n) time because the array is scanned once to build a frequency count and once more to evaluate lucky numbers. Hash map operations such as insert and lookup are O(1) on average. Space complexity is O(n) for the frequency map.
Find Lucky Integer in an Array Python or Java solution approach
Both Python and Java implementations typically use a dictionary or HashMap to count frequencies. After building the map, iterate through its entries and return the largest key where key == frequency. The logic remains identical across languages and runs in O(n) time.
Is Find Lucky Integer in an Array asked at Google, Amazon, or Meta?
This problem represents a common interview pattern involving frequency counting and hash tables. Variants of this pattern frequently appear in interviews at companies like Amazon and Google, especially in easy-to-medium array and hashing rounds.