x 128. Longest Consecutive Sequence

128. Longest Consecutive Sequence

With range

time: O(n)

space: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const set = new Set(nums);

    const ranges = {};

    let max = 0;
    for (const x of set) {
        const left = ranges[x - 1] ?? 0;
        const right = ranges[x + 1] ?? 0;
        const dis = right + left + 1;

        ranges[x] = dis;
        max = Math.max(max, dis);

        // TODO why?
        ranges[x - left] = dis;
        ranges[x + right] = dis;
    }

    return max;
};

4 6 3 2 8 1 5

0	1	2	3	4	5	6	7	8	9
	6	3	2	4	6	6		1

With Set

time: O(n)

Space: O(n)

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const set = new Set(nums);

    let max = 0;
    for (let i = 0; i < nums.length; i++) {
        const curr = nums[i];

        if (set.size === 0) break;

        if (!set.has(curr)) {
            continue;
        }

        let left = curr - 1;
        let right = curr + 1;
        while (set.delete(left)) {
            left--;
        }
        while (set.delete(right)) {
            right++;
        }

        max = Math.max(max, right - left - 1);

    }

    return max;
};

solutions

https://leetcode.com/problems/longest-consecutive-sequence/solutions/41055/my-really-simple-java-o-n-solution-accepted/

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);
            
            // keep track of the max length 
            res = Math.max(res, sum);
            
            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for(int i : nums) set.add(i);
        int ans = 0;
        for(int num : nums) {
            int left = num - 1;
            int right = num + 1;
            while(set.remove(left)) left--;
            while(set.remove(right)) right++;
            ans = Math.max(ans,right - left - 1);
            if(set.isEmpty()) return ans;//save time if there are items in nums, but no item in hashset.
        }
        return ans;
    }