# LeetCode 128. [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence)

contributed by < [Eric Lin](https://github.com/ericlinsechs) >

## Aim
* Refer [source code from Jserv's Linux Kernel Internals](https://hackmd.io/@sysprog/linux2022-quiz1#%E6%B8%AC%E9%A9%97-3) to solve [Longest Consecutive Sequence](https://leetcode.com/problems/longest-consecutive-sequence).
* Describe how the code works.

## code implementation

### Data structure

Use circular doubly-linked list structure from [include/linux/types.h](https://github.com/torvalds/linux/blob/master/include/linux/types.h):

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

* `seq_node`:
* `num`: integer number.
* `link`: Link for chaining elements having the same hash value in hash table.

struct seq_node {
    int num;
    struct list_head link;
};  

### find
* Generate hash value from the remainder.
* Due to the possibility of different key values producing the same hash value, it is necessary to access the hash table `heads[hash]` and check for a matching number.

static struct seq_node *find(int num, int size, struct list_head *heads)
{   
    struct seq_node *node;
    int hash = num < 0 ? -num % size : num % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (node->num == num)
            return node;
    }
    return NULL;
}

### longestConsecutive
* `node`: Used to represent each element in the sequence.
* `heads`: An array of linked list. Each index in the array corresponds to a hash value.
* `line 10`: Inserts each `num` (element) from the array `nums` into the appropriate linked list based on its hash value. It avoids duplicates using the find function.
* `line 19`: For each element in the array, it searches for a consecutive sequence by checking elements to the left and right. If the node is located in the linked list, deletes it to avoid duplicates.
* `line 42`: The length of the sequence is updated, and the maximum length is stored in the length variable.

int longestConsecutive(int *nums, int n_size)
{
    int hash, length = 0;
    struct seq_node *node;
    struct list_head *heads = malloc(n_size * sizeof(*heads));

    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; i < n_size; i++) {
        if (!find(nums[i], n_size, heads)) {
            hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
            node = malloc(sizeof(*node));
            node->num = nums[i];
            list_add(&node->link, &heads[hash]);
        }
    }

    for (int i = 0; i < n_size; i++) {
        int len = 0;
        int num;
        node = find(nums[i], n_size, heads);
        while (node) {
            len++;
            num = node->num;
            list_del(&node->link);
            free(node);

            int left = num, right = num;
            while ((node = find(--left, n_size, heads))) {
                len++;
                list_del(&node->link);
                free(node);
            }

            while ((node = find(++right, n_size, heads))) {
                len++;
                list_del(&node->link);
                free(node);
            }

            length = len > length ? len : length;
        }
    }
    
    free(heads);

    return length;
}

### Complete code
* Include `list.h` from [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h).

#include <stdio.h>                                                                                         
#include <stdlib.h>
#include "list.h"

struct seq_node {
  int num;
  struct list_head link;
};

static struct seq_node *find(int num, int size, struct list_head *heads) {
  struct seq_node *node;
  int hash = num < 0 ? -num % size : num % size;
  list_for_each_entry(node, &heads[hash], link) {
    if (node->num == num)
      return node;
  }
  return NULL;
}

int longestConsecutive(int *nums, int n_size) {
  int hash, length = 0;
  struct seq_node *node;
  struct list_head *heads = malloc(n_size * sizeof(*heads));
    for (int i = 0; i < n_size; i++)
        INIT_LIST_HEAD(&heads[i]);

  for (int i = 0; i < n_size; i++) {
    if (!find(nums[i], n_size, heads)) {
      hash = nums[i] < 0 ? -nums[i] % n_size : nums[i] % n_size;
      node = malloc(sizeof(*node));
      node->num = nums[i];
      list_add(&node->link, &heads[hash]);
    }
  }

  for (int i = 0; i < n_size; i++) {
    int len = 0;
    int num;
    node = find(nums[i], n_size, heads);
    while (node) {
      len++;
      num = node->num;
      list_del(&node->link);
      free(node);

      int left = num, right = num;

      while ((node = find(--left, n_size, heads))) {
        len++;
        list_del(&node->link);
        free(node);
      }

      while ((node = find(++right, n_size, heads))) {
        len++;
        list_del(&node->link);
        free(node);
      }

      length = len > length ? len : length;
    }
  }

  free(heads);

  return length;
}

int main() 
{
  int nums[6] = {100, 4, 200, 1, 3, 2}, len;
  len = longestConsecutive(nums, 6);
  printf("len: %d\n", len);

  int nums_2[10] = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
  len = longestConsecutive(nums_2, 10);
  printf("len: %d\n", len);

  return 0;
}

## Implement hash tables in the style of the Linux kernel

I use the same method on [Two sum](https://leetcode.com/problems/two-sum/). For more details, please refer [ericlinsechs: Leetcode 1. Two sum](https://hackmd.io/@ericlinsechs/two_sum).

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>

struct hlist_head {
  struct hlist_node *first;
};

struct hlist_node {
  struct hlist_node *next, **pprev;
};

typedef struct {
  int size;
  struct hlist_head *ht;
} map_t;

struct hash_key {
  int num;
  struct hlist_node node;
};

#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member)                                        \
  __extension__({                                                              \
    const __typeof__(((type *)0)->member) *__pmember = (ptr);                  \
    (type *)((char *)__pmember - offsetof(type, member));                      \
  })
#else
#define container_of(ptr, type, member)                                        \
  ((type *)((char *)(ptr)-offsetof(type, member)))
#endif
#endif

map_t *map_init(int size) {
  map_t *map = malloc(sizeof(map_t));
  if (!map)
    return NULL;

  map->size = size;
  map->ht = malloc(sizeof(struct hlist_head) * size);
  if (map->ht) {
    for (int i = 0; i < size; i++)
      (map->ht)[i].first = NULL;
  } else {
    free(map);
    map = NULL;
  }
  return map;
}

static struct hash_key *find_num(map_t *map, int num) {
  int hash = num < 0 ? -num % map->size : num % map->size;
  struct hlist_head *head = &(map->ht)[hash];
  for (struct hlist_node *p = head->first; p; p = p->next) {
    struct hash_key *kn = container_of(p, struct hash_key, node);
    if (kn->num == num)
      return kn;
  }
  return NULL;
}

void map_add(map_t *map, int num) {
  struct hash_key *kn = find_num(map, num);
  if (kn)
    return;

  kn = malloc(sizeof(struct hash_key));
  kn->num = num;

  int hash = num < 0 ? -num % map->size : num % map->size;
  struct hlist_head *h = &map->ht[hash];
  struct hlist_node *n = &kn->node, *first = h->first;

  n->next = first;
  if (first)
    first->pprev = &n->next;
  h->first = n;
  n->pprev = &h->first;
}

static inline void hlist_del(struct hlist_node *n) {
  struct hlist_node *next = n->next;
  struct hlist_node **pprev = n->pprev;

  *pprev = next;
  if (next)
    next->pprev = pprev;
}

int longestConsecutive(int *nums, int n_size) {
  int length = 0;

  map_t *map = map_init(n_size);

  for (int i = 0; i < n_size; i++) {
    if (!find_num(map, nums[i]))
      map_add(map, nums[i]);
  }

  for (int i = 0; i < n_size; i++) {
    int len = 0;
    int num;

    struct hash_key *kn = find_num(map, nums[i]);
    while (kn) {
      len++;
      num = kn->num;
      hlist_del(&kn->node);
      free(kn);

      int left = num, right = num;
      while (kn = find_num(map, --left)) {
        len++;
        hlist_del(&kn->node);
        free(kn);
      }

      while (kn = find_num(map, ++right)) {
        len++;
        hlist_del(&kn->node);
        free(kn);
      }

      length = len > length ? len : length;
    }
  }
  free(map->ht);
  free(map);

  return length;
}

int main() 
{
  int nums[6] = {100, 4, 200, 1, 3, 2}, len;
  len = longestConsecutive(nums, 6);
  printf("len: %d\n", len);

  int nums_2[10] = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
  len = longestConsecutive(nums_2, 10);
  printf("len: %d\n", len);

  return 0;
}