Longest Consecutive Sequence in an Array
MediumOnly start counting at a run's first element
Problem
Given an array nums of n integers. Return the length of the longest sequence of consecutive integers. The integers in this sequence can appear in any order.
Put everything in a set, then only start counting from numbers that have no left neighbour.
The idea
Put everything in a set, then for each value check whether value-1 is absent — if it is, this value begins a run, so walk forward counting. That check is what keeps the total work linear: every run is walked exactly once, never from the middle.
The trick
- Start a walk only when x-1 is not in the set.
- Total work is O(n) even though there is a loop inside a loop.
- Sorting also works and is O(n log n), which is fine when n is small.
Step 1 of 8. Brute force: from each number, keep searching for the next consecutive one. Values: 100, 4, 200, 1, 3, 2.
Search each run.
1for (const x of nums) {2 let len = 1, cur = x;3 while (set.has(cur + 1)) { cur++; len++; }4 best = Math.max(best, len);5}Input
- array
- [100, 4, 200, 1, 3, 2]
Memory
- i
- —
Output
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [100, 4, 200, 1, 3, 2]
- Output:
- 4
- Explanation:
- 1,2,3,4 form a run of length 4.
Example 2
- Input:
- nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
- Output:
- 9
- Explanation:
- 0..8 is a run of length 9.
Example 3
- Input:
- nums = [10]
- Output:
- 1
- Explanation:
- A single number is a run of length 1.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.