algoadvance

Leetcode 1394. Find Lucky Integer in an Array

Problem Statement:

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value. Write a function to return a lucky integer in the array. If there are multiple lucky integers return the largest of them. If there is no lucky integer return -1.

Clarifying Questions:

1. Input Constraints:
   • How large can the array be?
   • What is the range of integer values in the array?
2. Output:
   • What should be returned if no lucky integer is found?
3. Edge Cases:
   • What if the array is empty?
   • What if all elements in the array are the same?

Code:

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

class Solution {
public:
    int findLucky(std::vector<int>& arr) {
        // Hashmap to store the frequency of each number
        std::unordered_map<int, int> freqMap;
        
        // Calculate frequencies
        for (int num : arr) {
            freqMap[num]++;
        }
        
        int result = -1;  // Default result if no lucky integer is found
        
        // Iterate through the hashmap to find lucky integers
        for (const auto& elem : freqMap) {
            if (elem.first == elem.second) {
                result = std::max(result, elem.first);
            }
        }
        
        return result;
    }
};

// Example usage:
// int main() {
//     Solution sol;
//     std::vector<int> arr = {2, 2, 3, 4};
//     std::cout << sol.findLucky(arr) << std::endl;  // Output: 2
//     return 0;
// }

Strategy:

1. Frequency Mapping:
   • We use an unordered map to store the frequency of each integer in the array.
   • Traverse the array and update the frequency map accordingly.
2. Finding Lucky Integer:
   • Iterate through the frequency map to check if there is any integer whose frequency matches its value.
   • Keep track of the largest lucky integer found.
3. Return Result:
   • If a lucky integer is found, return the largest one; otherwise, return -1.

Time Complexity:

• Time Complexity:
  • Building the frequency map involves a single pass through the array: (O(n)).
  • Iterating through the elements of the frequency map adds another pass: (O(k)), where (k) is the number of unique elements (which in the worst case can be (O(n))).
  • Overall time complexity: (O(n)).
• Space Complexity:
  • Storing the frequency map requires additional space: (O(k)), where (k) is the number of unique elements.
  • Overall space complexity: (O(n)) in the worst case where all elements are unique.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?