#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1024
// Simple hash set using a fixed-size array
typedef struct {
int data[MAX_SIZE];
int size;
} IntSet;
int contains(IntSet* set, int value) {
for (int i = 0; i < set->size; i++) {
if (set->data[i] == value) return 1;
}
return 0;
}
void insert(IntSet* set, int value) {
if (!contains(set, value)) {
set->data[set->size++] = value;
}
}
int longestConsecutive(int* nums, int length) {
IntSet set = { .size = 0 };
for (int i = 0; i < length; i++) {
insert(&set, nums[i]);
}
int longestStreak = 0;
for (int i = 0; i < set.size; i++) {
int num = set.data[i];
// Check if the number just before this one (num - 1) is not in the set.
// If it's not, then num is the start of a new sequence.
// Example: If num = 3 and 2 is not in the set, then 3 starts a sequence.
if (!contains(&set, num - 1)) {
// Initialize the current sequence starting from num.
// Start counting with a streak of 1.
int currentNum = num;
int currentStreak = 1;
// Keep checking if the next number exists in the set.
// If it does, increment currentNum and increase the streak.
// This loop continues until the sequence breaks.
while (contains(&set, currentNum + 1)) {
currentNum++;
currentStreak++;
}
// Update the longest streak if the current one is longer.
if (currentStreak > longestStreak) {
longestStreak = currentStreak;
}
}
}
return longestStreak;
}
int main() {
int nums[] = {680, 4, 590, 3, 1, 2};
int length = sizeof(nums) / sizeof(nums[0]);
int result = longestConsecutive(nums, length);
printf("Length of the longest consecutive sequence: %d\n", result);
return 0;
}
/*
run:
Length of the longest consecutive sequence: 4
*/
