The algorithm is designed to find the longest consecutive sequence in an array of integers. It uses a HashSet to efficiently track the elements of the array and determine the length of the longest consecutive sequence. The key steps are:
Create a HashSet: Add all elements from the input array to a HashSet. This allows for O(1) time complexity for checking the existence of elements.
Iterate through the HashSet: For each element in the HashSet, check if it's the start of a new sequence. This is done by checking if (element - 1) is not in the HashSet. If it's the start of a new sequence, proceed to the next step.
Count Consecutive Elements: Starting from the current element, count the number of consecutive elements. This is done by incrementally checking for (currentElement + 1) in the HashSet, and incrementing the count each time a consecutive element is found.
Update the Longest Streak: If the count of consecutive elements is greater than the current longest streak, update the longest streak.
Return the Result: After iterating through all elements, return the longest streak found.
[x] Specified difficulty level, tag & Note(if any).
How Has This Been Tested?
Test Cases
To verify the efficacy of the code, the following test cases can be considered:
Normal Case:
Input: [100, 4, 200, 1, 3, 2]
Expected Output: 4 (since the longest consecutive sequence is [1, 2, 3, 4]).
Empty Array:
Input: []
Expected Output: 0 (as there are no elements).
Array with No Consecutive Numbers:
Input: [10, 5, 6]
Expected Output: 1 (since the longest consecutive sequence would be any of the single elements).
Array with Duplicates:
Input: [1, 2, 2, 3, 4]
Expected Output: 4 (ignoring the duplicate 2, the longest sequence is [1, 2, 3, 4]).
Large Range of Numbers:
Input: A large range of numbers with some gaps.
Expected Output: Length of the longest consecutive sequence in the given range.
Non-Sequential Array:
Input: [9, 1, 4, 7, 3]
Expected Output: 1 (as there are no consecutive sequences longer than a single number).
Pull Request Template
Description
The algorithm is designed to find the longest consecutive sequence in an array of integers. It uses a HashSet to efficiently track the elements of the array and determine the length of the longest consecutive sequence. The key steps are:
Create a HashSet: Add all elements from the input array to a HashSet. This allows for O(1) time complexity for checking the existence of elements.
Iterate through the HashSet: For each element in the HashSet, check if it's the start of a new sequence. This is done by checking if (element - 1) is not in the HashSet. If it's the start of a new sequence, proceed to the next step.
Count Consecutive Elements: Starting from the current element, count the number of consecutive elements. This is done by incrementally checking for (currentElement + 1) in the HashSet, and incrementing the count each time a consecutive element is found.
Update the Longest Streak: If the count of consecutive elements is greater than the current longest streak, update the longest streak.
Return the Result: After iterating through all elements, return the longest streak found.
Put check marks:
Have you made changes in README file ?
How Has This Been Tested?
Test Cases
To verify the efficacy of the code, the following test cases can be considered:
Normal Case: Input: [100, 4, 200, 1, 3, 2] Expected Output: 4 (since the longest consecutive sequence is [1, 2, 3, 4]).
Empty Array: Input: [] Expected Output: 0 (as there are no elements).
Array with No Consecutive Numbers: Input: [10, 5, 6] Expected Output: 1 (since the longest consecutive sequence would be any of the single elements).
Array with Duplicates: Input: [1, 2, 2, 3, 4] Expected Output: 4 (ignoring the duplicate 2, the longest sequence is [1, 2, 3, 4]).
Large Range of Numbers: Input: A large range of numbers with some gaps. Expected Output: Length of the longest consecutive sequence in the given range.
Non-Sequential Array: Input: [9, 1, 4, 7, 3] Expected Output: 1 (as there are no consecutive sequences longer than a single number).
Array with Negative Numbers: Input: [-1, -2, 0, 1, 2] Expected Output: 4 (sequence [-2, -1, 0, 1]).
Make sure all below guidelines are followed else PR will get Reject: