Longest Consecutive Sequence

                                            
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numSet(nums.begin(), nums.end());
        int longestStreak = 0;

        for (int num : nums) {
            if (numSet.find(num - 1) == numSet.end()) {
                int currentNum = num;
                int currentStreak = 1;

                while (numSet.find(currentNum + 1) != numSet.end()) {
                    currentNum++;
                    currentStreak++;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
};

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

                                            
class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num_set = set(nums)
        longest_streak = 0
        
        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1
                
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                
                longest_streak = max(longest_streak, current_streak)
        
        return longest_streak

                                            
public class Solution {
    public int LongestConsecutive(int[] nums) {
        if (nums == null || nums.Length == 0)
            return 0;
        
        HashSet<int> numSet = new HashSet<int>();
        foreach (int num in nums) {
            numSet.Add(num);
        }
        
        int longestStreak = 0;
        foreach (int num in numSet) {
            if (!numSet.Contains(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;
                
                while (numSet.Contains(currentNum + 1)) {
                    currentNum++;
                    currentStreak++;
                }
                
                longestStreak = Math.Max(longestStreak, currentStreak);
            }
        }
        
        return longestStreak;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const numSet = new Set(nums);
    let longestStreak = 0;

    for (let num of numSet) {
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
};

                                            
function longestConsecutive(nums: number[]): number {
    const numSet = new Set(nums);
    let longestStreak = 0;

    for (let num of numSet) {
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function longestConsecutive($nums) {
        $set = array_flip($nums);
        $longest = 0;
        
        foreach ($set as $num => $val) {
            if (!isset($set[$num - 1])) {
                $currentNum = $num;
                $currentStreak = 1;
                
                while (isset($set[$currentNum + 1])) {
                    $currentNum++;
                    $currentStreak++;
                }
                
                $longest = max($longest, $currentStreak);
            }
        }
        
        return $longest;
    }
}

                                            
class Solution {
    func longestConsecutive(_ nums: [Int]) -> Int {
        var numSet = Set(nums)
        var longestStreak = 0
        
        for num in numSet {
            if !numSet.contains(num - 1) {
                var currentNum = num
                var currentStreak = 1
                
                while numSet.contains(currentNum + 1) {
                    currentNum += 1
                    currentStreak += 1
                }
                
                longestStreak = max(longestStreak, currentStreak)
            }
        }
        
        return longestStreak
    }
}

                                            
class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        if(nums.isEmpty()) return 0
        
        val numSet = nums.toHashSet()
        var longestStreak = 0
        
        for(num in numSet){
            if(num - 1 !in numSet){
                var currentNum = num
                var currentStreak = 1
                
                while(currentNum + 1 in numSet){
                    currentNum++
                    currentStreak++
                }
                
                longestStreak = maxOf(longestStreak, currentStreak)
            }
        }
        
        return longestStreak
    }
}

                                            
class Solution {
  int longestConsecutive(List<int> nums) {
    Set<int> numSet = Set.from(nums);
    int longestStreak = 0;
    
    for (int num in numSet) {
      if (!numSet.contains(num - 1)) {
        int currentNum = num;
        int currentStreak = 1;
        
        while (numSet.contains(currentNum + 1)) {
          currentNum++;
          currentStreak++;
        }
        
        longestStreak = currentStreak > longestStreak ? currentStreak : longestStreak;
      }
    }
    
    return longestStreak;
  }
}

                                            
func longestConsecutive(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    longestStreak := 0
    for num := range numSet {
        if !numSet[num-1] {
            currentNum := num
            currentStreak := 1

            for numSet[currentNum+1] {
                currentNum++
                currentStreak++
            }

            if currentStreak > longestStreak {
                longestStreak = currentStreak
            }
        }
    }

    return longestStreak
}

                                            
# @param {Integer[]} nums
# @return {Integer}
def longest_consecutive(nums)
    set = Set.new(nums)
    longest_streak = 0
    
    set.each do |num|
        if !set.include?(num - 1)
            current_num = num
            current_streak = 1
            
            while set.include?(current_num + 1)
                current_num += 1
                current_streak += 1
            end
            
            longest_streak = [longest_streak, current_streak].max
        end
    end
    
    return longest_streak
end

                                            
object Solution {
    def longestConsecutive(nums: Array[Int]): Int = {
        if (nums.isEmpty) return 0

        val numSet = nums.toSet
        var longestStreak = 0

        for (num <- numSet) {
            if (!numSet.contains(num - 1)) {
                var currentNum = num
                var currentStreak = 1

                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1
                    currentStreak += 1
                }

                longestStreak = Math.max(longestStreak, currentStreak)
            }
        }

        longestStreak
    }
}

                                            
impl Solution {
    pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
        use std::collections::HashSet;

        let mut num_set: HashSet<i32> = nums.into_iter().collect();
        let mut longest_streak = 0;

        for &num in num_set.iter() {
            if !num_set.contains(&(num - 1)) {
                let mut current_num = num;
                let mut current_streak = 1;

                while num_set.contains(&(current_num + 1)) {
                    current_num += 1;
                    current_streak += 1;
                }

                longest_streak = longest_streak.max(current_streak);
            }
        }

        longest_streak
    }
}

To solve this coding challenge of finding the longest consecutive sequence in an unsorted array of integers, we can use the following approach. The main idea here is to utilize a hash set for O(1) average time complexity look-ups, ensuring that our overall algorithm can run in linear time, O(n).

Explanation:

Initialization:

First, if the array is empty, we return 0 immediately because there is no sequence in an empty array.
Next, we convert the array to a set. This helps in ensuring O(1) time complexity for look-ups, which is crucial for maintaining linear time complexity.

Finding the Starting Point of a Sequence:

For each number in the set, we check whether the number is the start of a potential sequence. This can be determined by checking if the number's predecessor is not in the set (i.e.,
num - 1

not in the set). If it is not, then the current number could be the start of a new sequence.

Tracking the Sequence Length:

For each potential starting number, we iterate to find the length of the consecutive sequence beginning with that number.
We keep a count of the current streak length and iterate through the next consecutive numbers (i.e.,
num + 1

,
num + 2

, etc.) until the next number is not found in the set.

Updating the Longest Streak:

During this process, we continuously update the
longest_streak

variable with the maximum length of all sequences found so far.

Return the Result:

Finally, we return the length of the longest consecutive sequence found.

Here’s the pseudocode representation:

                                            
# Function to find the longest consecutive sequence length
def findLongestConsecutiveSequence(nums):
# If the array is empty, return 0 immediately
if length of nums is 0:
return 0

# Convert array to a set to benefit from average O(1) time complexity look-ups
num_set = set(nums)

# Initialize the variable to keep track of the longest sequence length
longest_streak = 0

# Iterate through each number in the set
for number in num_set:
# If number - 1 is not in the set, then this might be the start of a sequence
if (number - 1) is not in num_set:
# Initialize variables for the current number and current streak length
current_num = number
current_streak = 1

# Continue to check for the next consecutive numbers in the sequence
while (current_num + 1) is in num_set:
# Move to the next number in the sequence
current_num += 1
# Increase the streak length
current_streak += 1

# Update the longest streak if the current streak is longer
longest_streak = maximum(longest_streak, current_streak)

# Return the length of the longest consecutive sequence found
return longest_streak

Detailed Steps in Pseudocode:

Handle Edge Case:

If the input array
nums

is empty, return 0 immediately as there are no sequences in an empty array.

Convert Array to Set:

Create a set
num_set

from
nums

. This conversion helps facilitate O(1) look-ups on average, which is critical for ensuring our algorithm runs in O(n) time.

Initialize Longest Streak Variable:

Create a variable
longest_streak

and set it to 0. This variable will keep track of the length of the longest consecutive sequence found during our iterations.

Iterate Through Each Number in the Set:

Loop through each
number

in
num_set

.

Identify the Start of a New Sequence:

For each
number

, check if
number - 1

is not in
num_set

. If true, it means
number

could be the start of a new sequence.

Track Current Sequence:

Initialize
current_num

with
number

and
current_streak

with 1.
Use a while loop to check if
current_num + 1

is in
num_set

. While it's true:

Increment
current_num

by 1.
Increment
current_streak

by 1.

Update Longest Streak:

After exiting the while loop, update
longest_streak

with the maximum of
longest_streak

and
current_streak

.

Return Result:

Finally, return the value of
longest_streak

as the length of the longest consecutive sequence.

By following these steps and the detailed pseudocode provided, you can implement an efficient algorithm to solve the problem of finding the longest consecutive sequence in a given unsorted array of integers.