Overflow corner case


  • 0
    D

    Please try this corner case:[2147483647, 2147483646, -2147483648], which is [INT_MAX, INT_MAX-1, INT_MIN]
    The correct result should be 2, but I got 3 from Leetcode. I think overflow situation need to be taken into account. The solution is still O(n) though.

    int longestConsecutive(vector<int>& nums) {
    		if (nums.empty()) return 0;
    		int l, r, ans = 0, tmp;
    		unordered_map<int, int> length;
    		for (int n : nums) {
    			if (length.find(n) != length.end()) continue;
    			auto foundl = length.find(n - 1), foundr = length.find(n + 1);
                            //If overflow, discard the iterator we found and set it to unordered_map::end
    			if (n == INT_MIN)
    				foundl = length.end();
    			if (n == INT_MAX)
    				foundr = length.end();
    			l = foundl == length.end() ? 0 : foundl->second;
    			r = foundr == length.end() ? 0 : foundr->second;
    			tmp = l + r +1;
    			ans = max(tmp, ans);
    			length[n] = tmp;
    			if (foundl != length.end()) {
    				length[foundl->first - l + 1] = tmp;
    			}
    			if (foundr != length.end()) {
    				length[foundr->first + r - 1] = tmp;
    			}
    		}
    		return ans;
    	}
    

Log in to reply
 

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