Coding

Longest Consecutive Sequence in an Array

Asked atZZupee

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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.

Input: nums = [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest sequence of consecutive elements in the array is [1, 2, 3, 4], which has a length of 4. This sequence can be formed regardless of the initial order of the elements in the array.

Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] Output: 9 Explanation: The longest sequence of consecutive elements in the array is [0, 1, 2, 3, 4, 5, 6, 7, 8], which has a length of 9.

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

```
 1 &lt;= nums.length &lt;= 105
```
** **-109 <= nums[i] <= 109

cpp

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        
    }
};

java

class Solution {
    public int longestConsecutive(int[] nums) {
    }
}

python

class Solution:
    def longestConsecutive(self, nums):

javascript

class Solution {
    longestConsecutive(nums){
      
    }
}

csharp

public class Solution
{
    public int LongestConsecutive(int[] nums)
    {
    }
}

func longestConsecutive(nums []int) int {
	//your code goes here
}

Stuck? Show a way to structure it+

01Insert numbers into a set
02For each value, test whether value-1 is absent
03Extend forward to count that run
04Keep the maximum length

Reference answer

Start by restating the input contract for Longest Consecutive Sequence in an Array and testing the smallest boundary case before choosing the algorithm. Put all values in a hash set. Start a run only from a value whose predecessor is absent; then extend forward while successive values exist. Each value is visited only as part of its unique run, giving expected linear time. Explain the invariant while coding, then show how each update preserves it. Hash-set operations give expected O(n) time and the set uses O(n) space. Walk through one nontrivial example aloud so the interviewer can see why the method reaches the intended result. Finally, call out input assumptions and failure cases rather than silently relying on them. A clean implementation should keep state local, use descriptive names, and avoid work that the invariant makes unnecessary.

Then expect these follow-ups

How would you return the sequence itself?
Tests: implementation extension
What assumptions underlie expected O(1) hashing?
Tests: follow-up reasoning

Hiring now

Software engineer roles are open right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY

Or practice this question first

Next question