algoadvance

Leetcode 1394. Find Lucky Integer in an Array

Problem Statement

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.

Clarifying Questions

  1. Q: What is the expected length of the input array?
    • A: The length of the array arr could be between 1 and 500.
  2. Q: What are the constraints on the elements of the array?
    • A: The elements are integers ranging from 1 to 500.
  3. Q: Is it acceptable to use extra space proportional to the input size?
    • A: Yes, using extra space proportional to the input size or the frequencies should be fine.

Strategy

  1. Frequency Counting:
    • We’ll first create a frequency map using a HashMap<Integer, Integer> where the key is the integer from the array and the value is its frequency.
  2. Finding the Lucky Integer:
    • Iterate through the frequency map to find keys where the key is equal to its frequency and keep track of the maximum of such keys.
  3. Edge Cases:
    • If no such key exists where key equals its frequency, return -1.

Code

import java.util.HashMap;
import java.util.Map;

public class FindLuckyInteger {
    public int findLucky(int[] arr) {
        // Step 1: Frequency counting using a HashMap
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : arr) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Finding the largest lucky integer
        int maxLucky = -1;
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            if (entry.getKey().equals(entry.getValue())) {
                maxLucky = Math.max(maxLucky, entry.getKey());
            }
        }
        
        return maxLucky;
    }

    public static void main(String[] args) {
        FindLuckyInteger solution = new FindLuckyInteger();
        
        int[] arr1 = {2, 2, 3, 4};
        int[] arr2 = {1, 2, 2, 3, 3, 3};
        int[] arr3 = {5};
        int[] arr4 = {7, 7, 7, 7, 7, 7, 7};

        System.out.println(solution.findLucky(arr1)); // Output: 2
        System.out.println(solution.findLucky(arr2)); // Output: 3
        System.out.println(solution.findLucky(arr3)); // Output: -1
        System.out.println(solution.findLucky(arr4)); // Output: 7
    }
}

Time Complexity

Given the constraints, both steps are efficient, making the overall time complexity O(n) and the space complexity O(k), with k ≤ 500. Thus, the algorithm is quite efficient for the given problem constraints.

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