Find Lucky Integer in an Array Leetcode Solution

Difficulty Level Easy
Frequently asked in Microsoft
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutionsViews 5192

Problem statement

In the problem ” Find Lucky Integer in an Array ” we are given an array where an integer is called lucky if its frequency in the array is equal to its value.

Our task is to return the largest lucky number. If no such number exists we have to return -1. Values in the array lie between 1 and 500 and the length of the array is a maximum of 500.

Example

arr = [2,2,3,4]
2

Explanation:

Find Lucky Integer in an Array Leetcode Solution

The frequency of 2 is 2 and the frequency of 3 and four is 1. As 2 is the only lucky integer so this is our answer.

Sorting Approach for Find Lucky Integer in an Array Leetcode Solution

As we want to count the number of occurrences of each number and then find the greatest element satisfying the given condition. To do this we will pick a number and then traverse the entire array to count its occurrences and then select the greatest element satisfying the condition. Here we need to traverse the complete array n times so the time complexity becomes O(n*n). We can increase the performance by sorting the array. This will bring the same numbers together. We will follow these steps:

  1. Sort the array in decreasing order.
  2. Count all occurrences of the encountered element if it satisfies the condition then return it.
  3.  In the end, if no element satisfies the condition then return -1.

Implementation

C++ code for Find Lucky Integer in an Array

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    sort(begin(arr), end(arr), greater<int>());
    int cnt = 1;
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] == arr[i - 1])
            ++cnt;
        else {
            if (arr[i - 1] == cnt)
                return cnt;
            cnt = 1;
        }
    }
    return arr.back() == cnt ? cnt : - 1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

Java code for Find Lucky Integer in an Array

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
public static int findLucky(int[] arr) {
    Arrays.sort(arr);
    int ans = 0;
    for (int i = arr.length - 1; i >= 0; i--) {
        ans++;
        if (i == 0 || arr[i] != arr[i - 1]) {
            if (ans == arr[i]) {
                return ans;
            }
            ans = 0;
        }
    }
    return -1;
}
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

Complexity Analysis of Find Lucky Integer in an Array Leetcode Solution

Time complexity

The time complexity of the above code is O(nlogn) because we are sorting the given array. Here n is the length of the given array.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store answer.

Hashing Approach for Find Lucky Integer in an Array Leetcode Solution

We can count the occurrences of each number in one go even without sorting with the help of hashing. We will follow these steps:

  1. Create a frequency array of size 501 as the value of the element could be a maximum of 500.
  2. Traverse the given array complete and store the count of each element in the frequency array.
  3. Now traverse the frequency array from the end and if any element satisfies the condition then return it.
  4.  In the end, if no element satisfies the condition then return -1.

Implementation

C++ code for Find Lucky Integer in an Array

#include <bits/stdc++.h> 
using namespace std; 
int findLucky(vector<int>& arr) {
    int m[501] = {};
    for (auto n : arr)
        ++m[n];
    for (auto n = arr.size(); n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
}

int main() 
{ 
vector<int> arr = {2,2,3,4}; 
 int ans=findLucky(arr);
 cout<<ans<<endl;
 return 0;
}
2

Java code for Find Lucky Integer in an Array

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static int findLucky(int[] arr) {
    int[] m = new int[501];
    for(int i=0;i<arr.length;i++)
        ++m[arr[i]];
    for (int n = arr.length; n > 0; --n)
        if (n == m[n])
            return n;
    return -1;
    }
  public static void main(String[] args) {
        int [] arr = {2,2,3,4}; 
        int ans=findLucky(arr); 
        System.out.println(ans);
  }
}
2

Complexity Analysis of Find Lucky Integer in an Array Leetcode Solution

Time complexity

The time complexity of the above code is O(n) because we are traversing the given array only once. Here n is the length of the given array.

Space complexity

The space complexity of the above code is O(n) because we are creating a hash table.

References

Translate »