Longest Consecutive Sequence
Longest Consecutive Sequence is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Previously Seen / Existence Check subpattern.
- Blind 75 · #8 of 75 · Arrays & Hashing
- NeetCode 150 · #9 of 150 · Arrays & Hashing
- NeetCode 250 · #18 of 250 · Arrays & Hashing
Problem statement
Given nums, an integer array, find the length of the longest consecutive sequence of distinct values. A consecutive sequence contains values that increase by exactly 1 from one value to the next; its values do not have to be adjacent in nums.
Duplicate values do not increase a sequence's length, and the original ordering of nums does not matter. Return 0 if nums is empty. The algorithm must run in O(n) time, where n is the length of nums.
Example 1:
Input: nums = [14,9,11,10,13,15,15,2] Output: 3 Explanation: The longest consecutive sequences are 9, 10, 11 and 13, 14, 15. Each has length 3; 12 is missing, so they cannot form one longer sequence.
Example 2:
Input: nums = [21,18,24,19,23,22,40,20] Output: 7 Explanation: The values 18 through 24 are all present, forming a consecutive sequence of length 7.
Example 3:
Input: nums = [] Output: 0 Explanation: An empty array contains no values, so its longest consecutive sequence has length 0.
Constraints:
- 0 <= nums.length <= 10^5 - -10^9 <= nums[i] <= 10^9 - Each element of nums is an integer. - nums may contain duplicate values.
Topics and companies
Topics: Array, Hash Table, Counting.
How to practise Longest Consecutive Sequence on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) expected time and O(n) space.
Open Longest Consecutive Sequence in the code editor, or read the Longest Consecutive Sequence editorial for a worked solution with its approach and complexity analysis.
Where Longest Consecutive Sequence sits in the DSA pattern sheet
- Array/Matrix Manipulation Patterns pattern guide
- Hashing - Previously Seen / Existence Check subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Longest Consecutive Sequence
Other problems that use the same Hashing - Previously Seen / Existence Check and Array/Matrix Manipulation Patterns techniques:
- Contains Duplicate — Easy, same subpattern
- Design HashSet — Easy, same subpattern
- Valid Sudoku — Medium, same subpattern
- Add Binary — Easy, same pattern
- Add to Array-Form of Integer — Easy, same pattern
- Concatenation of Array — Easy, same pattern