Finding the Longest Consecutive Sequence in a Circular Range
Problem Description
Given an array of integers representing week numbers (1-52), find the length of the longest consecutive sequence. The sequence can wrap around from week 52 to week 1, treating the range as circular.
Theoretical Approach
Preprocessing:
Remove duplicates from the input array.
Sort the array to ensure proper ordering.
Consecutive Check:
- Define a function to check if two numbers are consecutive, considering the circular nature of the range (52 is consecutive to 1).
Sequence Counting:
- Iterate through the array, for each element: a. Count consecutive elements following it. b. If reaching the end of the array, check if the sequence wraps around to the beginning.
Handling Wrap-around:
When checking consecutiveness, use modular arithmetic to handle the transition from 52 to 1.
Consider sequences that might start at any point in the array and potentially wrap around.
Tracking Maximum:
- Keep track of the longest sequence found so far, updating it whenever a longer sequence is discovered.
Result:
- After checking all possible starting points, return the length of the longest consecutive sequence found.
This approach ensures that all possible sequences are considered, including those that wrap around the circular range, providing a solution that works for any valid input within the specified constraints.
export function longestConsecutiveSequence(sortedArray: number[]): number {
let longestSequence = 0;
const uniqueSortedArray = [...new Set(sortedArray)].sort((a, b) => a - b);
for (let i = 0; i < uniqueSortedArray.length; i++) {
if (i === 0 || uniqueSortedArray[i - 1] + 1 !== uniqueSortedArray[i]) {
let currentSequence = 2;
while (
i + 1 < uniqueSortedArray.length &&
(uniqueSortedArray[i] % 53) + 1 === uniqueSortedArray[i + 1]
) {
i++;
currentSequence++;
}
// Wrap-around case
if (
i !== uniqueSortedArray.length - 1 &&
(uniqueSortedArray[i] % 53) + 1 === uniqueSortedArray[0]
) {
let k = 0;
while (
k < i &&
(uniqueSortedArray[
(k + uniqueSortedArray.length - 1) % uniqueSortedArray.length
] %
53) +
1 ===
uniqueSortedArray[k]
) {
currentSequence++;
k++;
}
}
longestSequence = Math.max(longestSequence, currentSequence);
}
}
return longestSequence;
}