C++ Solution


  • 3
    class Solution {
    public:
        int findLHS(vector<int>& nums) {
            map<int, int> freqs;
            for (int n : nums) {
                freqs[n]++;
            }
    
            int longest = 0;
            int lastNum = 0;
            int lastFreq = 0;
            for (pair<int, int> p : freqs) {
                int freq2 = 0;
                if (lastFreq && p.first == lastNum + 1) {
                    freq2 = p.second + lastFreq;
                }
                longest = max(longest, freq2);
                lastNum = p.first;
                lastFreq = p.second;
            }
            return longest;
        }
    };
    

  • 0
    Z

    @alexander Good solution! You idea is similar to sorting. unordered_map is required for O(n) time complexity.


  • 0

    @zestypanda Thanks. Yes I agree sorted map is not necessary given that you can probe the neighber.


  • 0
    W

    Really great solution! using map default comparator (less).
    I made a slight change to reduce some judgements.

    class Solution {
    public:
        int findLHS(vector<int>& nums) {
            map<int, int> freqs;
            for (int n : nums) {
                freqs[n]++;
            }
                
            int lastNum = freqs.begin()->first;
            int lastFreq = 0;
            int longest = 0;
            for (pair<int, int> p : freqs) {
                int freq2 = 0;
                if (p.first == lastNum + 1) {
                    freq2 = p.second + lastFreq;
                }
                longest = max(longest, freq2);
                lastNum = p.first;
                lastFreq = p.second;
            }
            return longest;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.