Skip to content

← leetcode

Find Lucky Integer in an Array

· Easy

LeetCode problem 1394

Just sort the array first and iterate through the entirety of arr from back to front, then simply returning the first number you see where its count is equal to itself (since the array is sorted from smallest to largest).

If there does not exist any number where this occurs, just return -1.

code

class Solution {
public:
    int findLucky(vector<int>& arr) {
        sort(arr.begin(), arr.end());

        int count = 1;
        int curr = arr.back();
        for (int i = arr.size()-2; i >= 0; --i) {
            if (curr == arr[i]) {
                ++count;
            } else {
                if (count == curr) {
                    return curr;
                }
                curr = arr[i];
                count = 1;
            }
        }
        if (count == curr) {
            return curr;
        }
        return -1;
    }
};

complexity

  • Time: O(n log(n)) where n is the size of arr
  • Space: O(1)

time taken

  • i forgot to time-