Scale Engineer

Find Lucky Integer in an Array

Easy
#1291Time: O(N^2), where N is the number of elements in the array. The nested loops cause us to perform N * N comparisons.Space: O(1), as we only use a few variables to store the count and the result, regardless of the input size.
Patterns
Counting
Data structures
ArrayHash Table

Prompt

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.

 

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.

 

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach involves iterating through each element of the array and for each element, counting its occurrences by iterating through the array again. This is the most straightforward but least efficient method.

Algorithm

  • 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.

Walkthrough

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.

class Solution {    public int findLucky(int[] arr) {        int largestLucky = -1;        // Using a Set to only check unique numbers can be a small optimization,        // but the core complexity remains the same if we recount for each.        for (int i = 0; i < arr.length; i++) {            int count = 0;            for (int j = 0; j < arr.length; j++) {                if (arr[j] == arr[i]) {                    count++;                }            }            if (count == arr[i]) {                largestLucky = Math.max(largestLucky, arr[i]);            }        }        return largestLucky;    }}

Complexity

Time

O(N^2), where N is the number of elements in the array. The nested loops cause us to perform N * N comparisons.

Space

O(1), as we only use a few variables to store the count and the result, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra space (O(1) space complexity).

Cons

  • Very inefficient for large arrays, with a quadratic time complexity.

  • Likely to result in a 'Time Limit Exceeded' error on competitive programming platforms for larger inputs.

Solutions

class Solution { public int findLucky ( int [] arr ) { int [] cnt = new int [ 510 ]; for ( int x : cnt ) { ++ cnt [ x ]; } int ans = - 1 ; for ( int x = 1 ; x < cnt . length ; ++ x ) { if ( cnt [ x ] == x ) { ans = x ; } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem