C++ O(N) solution with explanation


  • 0
    H

    Idea is simple. When there is not existing range, the new number will build up a range with length 1 and its lower and upper boundaries are 1. Now, imagine we have 1 existing range [i, j] (i <=j). For any new number x, there are 3 cases:

    • i <= x <= j : x has no impact to existing range, no action needed
    • x < i-1 || x > j+1: x has no impact to existing range, but it will set up a new range [x,x]
    • x == i-1 || x == j+1: x extends the existing range. This is what we need to handle.

    Based the analysis above, we can use a hash map to store the inserted numbers (key) and range length (value). For each new number, check if it hit the number right outside the range and update accordingly.

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_map<int, int> m;
            int res = 0;
            for (auto x : nums) {
                // already in an existing range, no impact
                if (m.count(x)) continue;
                int lower = m.count(x-1) ? m[x-1] : 0;
                int upper = m.count(x+1) ? m[x+1] : 0;
                m[x] = lower + upper + 1;
                m[x-lower] = m[x];
                m[x+upper] = m[x];
                res = max(res, m[x]);
            }
            return res;
        }
    };
    

Log in to reply
 

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