8. Longest Consecutive Sequence

MediumArrays, Hashing & Prefix SumsAlso on LeetCode ↗

Return the length of the longest run of consecutive integers (like 4, 5, 6, 7) that can be formed from the values in nums. The values do not need to be adjacent in the array. Aim for O(n).

Example 1

Input: nums = [10,4,20,1,3,2]

Output: 4

Explanation: The run is 1, 2, 3, 4.

Example 2

Input: nums = [9,1,-1,8,0,10,2]

Output: 4

Explanation: The run is -1, 0, 1, 2.

Constraints

0 ≤ nums.length ≤ 10⁵

Hint 1

Put everything in a set.

Hint 2

Only start counting from numbers that have no left neighbour (x − 1 is missing).

Hash TableUnion Find

Reference solution for Hash set, start of runs (time O(n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 not in s:          # x starts a run
                y = x
                while y + 1 in s:
                    y += 1
                best = max(best, y - x + 1)
        return best

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int x : nums) s.add(x);
        int best = 0;
        for (int x : s) {
            if (s.contains(x - 1)) continue;   // only start counting at the beginning of a run
            int y = x;
            while (s.contains(y + 1)) y++;
            best = Math.max(best, y - x + 1);
        }
        return best;
    }
}

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int best = 0;
        for (int x : s) {
            if (s.count(x - 1)) continue;      // only start counting at the beginning of a run
            int y = x;
            while (s.count(y + 1)) y++;
            best = max(best, y - x + 1);
        }
        return best;
    }
};

function longestConsecutive(nums) {
  const s = new Set(nums);
  let best = 0;
  for (const x of s) {
    if (s.has(x - 1)) continue; // only start counting at the beginning of a run
    let y = x;
    while (s.has(y + 1)) y++;
    best = Math.max(best, y - x + 1);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language