Struggling with the “Longest Consecutive Sequence” problem on LeetCode? This blog will help you understand the problem, walk you through three different solutions (Brute Force, Better, and Optimal), and explain every step. Let\u2019s get started!<\/p>\n\n\n\n
Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n You are given an unsorted array of integers. Your task is to find the length of the longest sequence of consecutive numbers (numbers that come one after another, like 1, 2, 3, 4) in the array. The sequence elements can be in any order in the input array.<\/p>\n\n\n\n Input:<\/strong> Explanation:<\/strong> Input:<\/strong> Let\u2019s break down the simplest way to solve this problem:<\/p>\n\n\n\n Why does this work?<\/strong>What Does the Problem Say?<\/h2>\n\n\n\n
Example 1<\/h3>\n\n\n\n
arr = [100, 4, 200,<\/code> 1, 3, 2 ]<\/p>\n\n\n\n
The longest consecutive sequence is `[1, 2, 3, 4] the answer is 4.<\/p>\n\n\n\nExample 2<\/h3>\n\n\n\n
arr = [0, 3, 7, 2, 5, 8, 4, 6, 0<\/code>]<\/p>\n\n\n\nExplanation: The longest consecutive sequence is <\/code>[0, 1, 2, 3, 4, 5, 6, 7, is 9.<\/p>\n\n\n\nBrute Force Solution<\/h2>\n\n\n\n
Intuition and Approach<\/h3>\n\n\n\n
\n
For every number in the array, try to build the longest consecutive sequence starting from that number.<\/li>\n\n\n\n
For each starting number, keep checking if the next number (num + 1<\/code>) exists in the array. If yes, increase your count and check for the next number.<\/li>\n\n\n\n
Keep track of the largest count you find for any starting number. This will be your answer.<\/li>\n<\/ol>\n\n\n\n
We are trying every possible starting point and counting how far we can go consecutively. It\u2019s simple but can be slow for large arrays because we keep searching the array for each next number.<\/p>\n\n\n\nCode Implementation<\/h3>\n\n\n\n