1394. Find Lucky Integer in an Array

Description

Given an array of integers arr, a lucky integer is an integer which has a frequency in the array equal to its value.

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.

 

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.

Example 4:

Input: arr = [5]
Output: -1

Example 5:

Input: arr = [7,7,7,7,7,7,7]
Output: 7

 

Constraints:

• 1 <= arr.length <= 500
• 1 <= arr[i] <= 500

My Solution

Source Code

/**
 * @param {number[]} arr
 * @return {number}
 */
let findLucky = function (arr) {
  let map = new Map();
  arr.forEach((i) => {
    //insert into the map the first time this element is found
    if (!map.get(i)) {
      map.set(i, 1);
    } else {
      //increment the counter in the map
      map.set(i, map.get(i) + 1);
    }
  });

  let lucky = -1;
  map.forEach((key, value) => {
    if (key == value && key >= lucky) {
      lucky = key;
    }
  });

  return lucky;
};

Analysis

For this problem I just used a simple hash map where the key-value pairs are (k, frequency(k)) where k is some integer in arr. We iterate over the array and increment the counter for each value. Then after that we iterate over the keys in the map to actually find the lucky integers which is when for the key-value pair (k, frequency(k)), k == frequency(k).

Iterating over the array is O(n) where n is the length of the array. Inserting into and retrieving from the hash map is O(1) so amortized O(n) overall to record all the array values and their frequencies. To locate the lucky integers, we iterate over the keys of the hash map. In the worst case, arr consists of only unique integers so the map contains n keys so iterating over them is O(n). All in all, the entire running time is simply O(n).