Scale Engineer

Longest Consecutive Sequence

Med
#0128Time: O(n^3)Space: O(1)30 companies
Algorithms
Union Find
Data structures
ArrayHash Table
Companies
AtlassianByteDanceCiscoEPAM Systems

Prompt

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

 

Example 1:

[1, 2, 3, 4]

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach iterates through each number in the array. For each number, it attempts to build a sequence by repeatedly checking if the next consecutive number exists anywhere else in the array. This check is done via a linear scan.

Algorithm

  • Initialize a variable maxLength to 0.\n- For each number num in the input array nums:\n - Initialize currentNum = num and currentLength = 1.\n - Start a loop:\n - Check if currentNum + 1 exists in the nums array by performing a linear scan.\n - If it exists, increment currentLength, update currentNum to currentNum + 1, and continue the loop.\n - If it does not exist, break the loop.\n - Update maxLength = max(maxLength, currentLength).\n- After iterating through all numbers, return maxLength.

Walkthrough

The brute-force algorithm iterates through every number in the input array nums. For each number num, it assumes it could be the start of a consecutive sequence. It then enters a while loop, checking for the existence of num + 1, num + 2, and so on. The check for existence is performed by another linear scan through the entire array. The length of the current sequence is tracked, and the maximum length found across all possible starting numbers is returned. This method is straightforward to conceptualize but is highly inefficient due to the nested loops and repeated scans.\n\n

java\nclass Solution {\n    private boolean arrayContains(int[] arr, int num) {\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] == num) {\n                return true;\n            }\n        }\n        return false;\n    }\n\n    public int longestConsecutive(int[] nums) {\n        if (nums.length == 0) {\n            return 0;\n        }\n\n        int longestStreak = 0;\n\n        for (int num : nums) {\n            int currentNum = num;\n            int currentStreak = 1;\n\n            while (arrayContains(nums, currentNum + 1)) {\n                currentNum += 1;\n                currentStreak += 1;\n            }\n\n            longestStreak = Math.max(longestStreak, currentStreak);\n        }\n\n        return longestStreak;\n    }\n}\n

Complexity

Time

O(n^3)

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

  • Uses constant extra space, O(1).

Cons

  • Extremely inefficient with a time complexity of O(n^3), making it impractical for even moderately sized inputs.

  • Will result in a 'Time Limit Exceeded' error on most coding platforms.

Solutions

class Solution { public int longestConsecutive ( int [] nums ) { Set < Integer > s = new HashSet <>(); for ( int x : nums ) { s . add ( x ); } int ans = 0 ; for ( int x : nums ) { if (! s . contains ( x - 1 )) { int y = x + 1 ; while ( s . contains ( y )) { ++ y ; } ans = Math . max ( ans , y - x ); } } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem