Solved: The Longest Consecutive Sequence Puzzle For Given Unsorted Array

In the realm of array manipulation, the search for the longest consecutive sequence poses an intriguing challenge. In this blog, we will explore the concept of a consecutive sequence and delve into the problem of finding the longest consecutive sequence in an array of integers. We will discuss the problem statement, explore potential approaches, and provide detailed implementations in both Java and Python.

 

Problem Statement:

Given an unsorted array of integers, our goal is to find the length of the longest consecutive sequence present in the array. A consecutive sequence is defined as a sequence of integers in which each consecutive number is exactly one greater than the previous number.

 

Example:

Consider the array [100, 4, 200, 1, 3, 2]. In this case, the longest consecutive sequence is [1, 2, 3, 4], with a length of 4.

 

Approach:

To solve the problem of finding the longest consecutive sequence, we can utilize a hash set to efficiently check for consecutive numbers. We will iterate through the array and add all the numbers to the set. Then, for each number in the array, we will check if its previous number (number - 1) exists in the set. If it doesn't, we will start counting the consecutive sequence from that number. We will update the maximum length of the consecutive sequence as we iterate through the array.

1. Initialize variables for the maximum length and a hash set to store the numbers.
2. Add all the numbers from the array to the set.
3. Iterate through the array:
   • For each number, check if its previous number (number - 1) exists in the set.
   • If it doesn't, start counting the consecutive sequence from that number:
     • Increment the current number by 1 and check if it exists in the set.
     • Keep incrementing the current number and updating the maximum length until the current number does not exist in the set.
   • Update the maximum length if necessary.
4. Return the maximum length of the consecutive sequence.

 

Java Implementation:

 

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {
    public static int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        
        int maxLength = 0;
        
        for (int num : nums) {
            if (!set.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                while (set.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
    
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        int length = longestConsecutive(nums);
        System.out.println("Length of the longest consecutive sequence: " + length);
    }
}

 

Python Implementation:

def longest_consecutive(nums):
    num_set = set(nums)
    max_length = 0
    
    for num in nums:
        if num - 1 not in num_set:
            current_num = num
            current_length = 1
            
            while current_num + 1 in num_set:
                current_num += 1
                current_length += 1
            
            max_length = max(max_length, current_length)
    
    return max_length

nums = [100, 4, 200, 1, 3, 2]
length = longest_consecutive(nums)
print("Length of the longest consecutive sequence:", length)

 

Conclusion:

The quest for the longest consecutive sequence within an unsorted array presents an intriguing challenge. By utilizing a hash set and efficient iteration, we can identify and compute the length of the longest consecutive sequence. The Java and Python implementations provided in this blog showcase the effectiveness of this approach. Armed with this knowledge, you can confidently tackle similar array manipulation challenges and enhance your problem-solving skills.