C++ O(N) solution walking the longest streak - Accepted


  • 0
    T

    In a first sweep, we store all the elements in an unordered map that maps the element to it's chain length. We use a second map to keep track of the elements of the sequence we already visited.

    In a second sweep, we start walking successors by checking if the successor is in the map. While we are walking the sequence, we increment the length and mark the successor as visited. If we encounter a successor we have already visited, we can simply take over it's chain length.

    This is O(N) because we walk each element in the map exactly once (That's why we keep the visited map). The idea is similar to a graph traversal where successors are edges.

    For a better explanation look at Stefan Pochmann's solution here.

    class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            // records the length starting at nums[i]
            unordered_map<int, int>  chainLength;
            // tracks if we already visited nums[i] in our sweep
            unordered_map<int, bool> visited;
            
            // fill in the maps
            for (int i=0; i<nums.size(); ++i) {
                chainLength[nums[i]] = 1;
                visited[nums[i]] = false;
            }
            
            // follow the successor to form a chain
            int maxLen = 0;
            for (int i=0; i<nums.size(); ++i) {
                
                // we already visited this element
                if (visited[nums[i]]) { continue; }
                
                // follow the chain of this element
                int next = nums[i] + 1;
                int len  = 0;
                while (visited.count(next)) {
                    if (visited[next]) {
                        len += chainLength[next];
                        break;
                    }
                    else {
                        ++len;
                        visited[next] = true;
                    }
                    ++next;
                }
                
                // record the chain length and mark visited
                chainLength[nums[i]] += len;
                visited[nums[i]] = true;
                
                // check if we improve the chain length
                maxLen = max(maxLen, chainLength[nums[i]]);
            }
            
            return maxLen;
        }
    };
    

Log in to reply
 

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