Longest Consecutive Sequence - LeetCode Solution and Approach

  

 128. Longest Consecutive Sequence - LeetCode - Medium

Solve this problem in LeetCode

Problem Description:

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:

Input: nums = [100,4,200,1,3,2]

Output: 4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

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

Output: 9

Constraints:

0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

Approach:

In this problem we have to find length of the longest consecutive elements sequence. In simple words, we need to find the largest range of numbers. We can use Set to store numbers, as we can use contains method in approx O(1) time. Set will also remove duplicates numbers.

We will find the starting point of the range and will iterate through the end of range to find its length. Once we get the length of range, we will find the maximum length among other lengths.

• If given array contains no element or only 1 element, the longest consecutive sequence will be 0 or 1 respectively. So need to check further.
•  We will store the array numbers in Set and will iterate through set.
• During iterating, we will check if set doesn't contain previous number (n-1). It means its starting of a range.
• Now we found the starting of range. We will iterate through the range and count number of elements. After iterating we will take the highest count and store in variable say maxK.
• We will continue iterating set elements. After iterating we will get the result in maxK.

JAVA:

Time Complexity : 0(n)

Space Complexity: 0(n)

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length <= 1) return nums.length;

        int maxK = 0;
        Set<Integer> set = new HashSet<>();
        
        for (int n : nums) set.add(n);

        for (int n : set) {
            if (!set.contains(n - 1)) { // if number is starting of value of range
                int nextValue = n + 1; 
                int k = 1;
                while (set.contains(nextValue++)) k++; // counting next values
                maxK = Math.max(maxK, k); // storing maximum count
                
            }
        }

        return maxK;
    }
}

Keep Learning and Practicing with Programming Chaska !!!