Find Lucky Integer in an Array

• Initialize a variable largestLucky to -1.
• Iterate through the input array arr with an outer loop from index i = 0 to n-1.
• For each element arr[i], initialize a count to 0.
• Start an inner loop from index j = 0 to n-1 to count the occurrences of arr[i].
• If arr[j] is equal to arr[i], increment count.
• After the inner loop completes, check if count is equal to the value arr[i].
• If they are equal, it means arr[i] is a lucky number. Update largestLucky to be the maximum of its current value and arr[i].
• After the outer loop completes, return largestLucky.

The brute-force method checks every number in the array to see if it's a lucky number. For each number x at index i, we perform a full scan of the array to count how many times x appears. If this count is equal to the value of x, we compare it with the largest lucky number found so far and update it if x is larger. This process is repeated for all numbers in the array.

1class Solution {2    public int findLucky(int[] arr) {3        int largestLucky = -1;4        // Using a Set to only check unique numbers can be a small optimization,5        // but the core complexity remains the same if we recount for each.6        for (int i = 0; i < arr.length; i++) {7            int count = 0;8            for (int j = 0; j < arr.length; j++) {9                if (arr[j] == arr[i]) {10                    count++;11                }12            }13            if (count == arr[i]) {14                largestLucky = Math.max(largestLucky, arr[i]);15            }16        }17        return largestLucky;18    }19}

• Sort the input array arr in non-decreasing order.
• Initialize largestLucky to -1.
• Iterate through the sorted array using a pointer i.
• At each position i, find the end of the contiguous block of the same number arr[i]. Let's say this block ends at index j-1.
• The frequency of arr[i] is j - i.
• If the frequency (j - i) is equal to the value arr[i], then arr[i] is a lucky number. Update largestLucky with arr[i].
• Move the pointer i to j to start checking the next distinct number.
• Repeat until the end of the array is reached.
• Return largestLucky.

By sorting the array, all equal elements become adjacent. This allows us to count the frequency of each number in a single pass. We can iterate through the array, and for each distinct number, we count how many times it appears consecutively. If this count matches the number's value, we identify it as a lucky number and update our potential answer. Since we process numbers in increasing order, the last lucky number we find will be the largest one.

1import java.util.Arrays;2 3class Solution {4    public int findLucky(int[] arr) {5        Arrays.sort(arr);6        int largestLucky = -1;7        int i = 0;8        while (i < arr.length) {9            int j = i;10            while (j < arr.length && arr[j] == arr[i]) {11                j++;12            }13            int count = j - i;14            if (count == arr[i]) {15                largestLucky = arr[i]; // Last lucky number found will be the largest16            }17            i = j;18        }19        return largestLucky;20    }21}

• Create a HashMap<Integer, Integer> to store the frequency of each number.
• Iterate through the input array arr. For each num in arr, update its count in the hash map.
• Initialize largestLucky to -1.
• Iterate through the entries of the hash map. For each entry (key, value):
• Check if the number (key) is equal to its frequency (value).
• If key == value, it's a lucky number. Update largestLucky = Math.max(largestLucky, key).
• After checking all entries, return largestLucky.

This approach uses a hash map to efficiently count the frequency of each number in the array. We traverse the input array once, and for each number, we increment its corresponding count in the map. After building the frequency map, we iterate through its key-value pairs. If a key (the number) is equal to its value (the frequency), we've found a lucky number. We keep track of the largest such number found.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int findLucky(int[] arr) {6        Map<Integer, Integer> freqMap = new HashMap<>();7        for (int num : arr) {8            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);9        }10 11        int largestLucky = -1;12        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {13            int num = entry.getKey();14            int freq = entry.getValue();15            if (num == freq) {16                largestLucky = Math.max(largestLucky, num);17            }18        }19        return largestLucky;20    }21}

• Create an integer array counts of size 501 (since values are from 1 to 500).
• Iterate through the input array arr. For each num, increment counts[num].
• To find the largest lucky number, iterate from i = 500 down to 1.
• At each i, check if counts[i] is equal to i.
• If counts[i] == i, then i is a lucky number. Since we are iterating downwards, this is the largest one. Return i immediately.
• If the loop completes without finding any lucky number, return -1.

This is an optimization of the hash map approach, tailored to the problem's constraints. Since we know the numbers are all within the range [1, 500], we can use a fixed-size array (of size 501) to store frequencies. The index of the array corresponds to the number, and the value at that index is its frequency. After populating this frequency array in one pass, we can perform a second pass. To find the largest lucky number efficiently, we iterate downwards from 500 to 1. The first index i we find where counts[i] == i will be our answer.

1class Solution {2    public int findLucky(int[] arr) {3        int[] counts = new int[501]; // Constraints: 1 <= arr[i] <= 5004        for (int num : arr) {5            counts[num]++;6        }7 8        for (int i = 500; i >= 1; i--) {9            if (counts[i] == i) {10                return i; // Found the largest lucky number11            }12        }13 14        return -1; // No lucky number found15    }16}