My Accepted O(n) C++ code with one unordered_map (explained)


  • 1
    J

    (1)The values are added to an unordered_map.

    (2) Scan the unordered_map for consecutive values. Here I use a boolean flag (stored in the unordered map) to note whether that value is already scanned/visited. At each value (that is not already visited), search for decreasing sequence (ie. the presence of value - 1, value -2, etc in the unordered map). Then search for the increasing sequence. Increase the length accordingly.

    The use of visited flag makes sure that unordered_map scan is O(n) (any value will be visited twice at most 1. in scanning the map, 2. in finding a sequence)

    Let me know if you have any question.

    Thanks.

    int longestConsecutive(vector<int> &num) {
    unordered_map<int, bool> um;
    typedef pair<int,bool> umpair;
    for (int i = 0; i < num.size(); i++)
    	um.insert(umpair(num[i], false));
    
    int maxLen = 0;
    for (auto start = um.begin(); start != um.end(); start++)
    {		
    	if (start->second == true)
    		continue;
    	int len = 1;
    	auto cur = start;
    	cur->second = true;
    
        //find decreasing values seq from current value
    	while (um.find(cur->first -1) != um.end())
    	{
    		cur = um.find(cur->first - 1);
    		len++;
    		cur->second = true;
    	}
    
        //find increasing values seq from current value
    	cur = start;
    	while (um.find(cur->first + 1) != um.end())
    	{
    		cur = um.find(cur->first + 1);
    		len++;
    		cur->second = true;
    	}
    	if (len > maxLen)
    		maxLen = len;
    }
    return maxLen;
    

    }


Log in to reply
 

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