#include <stdlib.h>

#define HASH_SIZE 5000

// use linked list to handle collisions
typedef struct node{
  unsigned int value;
  struct node* next;
} node;

void node_free(node* head) {
  node* tmp;
  while(head != NULL) {
    tmp = head;
    head = head->next;
    free(tmp);
  }
}

static node* hash_arr[HASH_SIZE];

void hash_free() {
  for (int i = 0; i < HASH_SIZE; i++) {
    if (hash_arr[i] != NULL) {
      node_free(hash_arr[i]);
    }
  }
}

static int hash(int key) {
  return abs(key) % HASH_SIZE;
}

static int hash_insert(int key, int value) {
  node* node = malloc(sizeof(struct node));
  node->value = value;
  node->next = NULL;
  unsigned int hash_index = hash(key);
  if (hash_arr[hash_index] == NULL) {
    hash_arr[hash_index] = node;
    return 0;
  }
  node->next = hash_arr[hash_index];
  hash_arr[hash_index] = node;
  return 0;
  return -1;
}

static int hash_find(int key, int* nums) {

  unsigned int hash_index = hash(key);
  if (hash_arr[hash_index] != NULL) {
    node* curr_node = hash_arr[hash_index];
    while(nums[curr_node->value] != key) {
      curr_node = curr_node->next;
    }
    return curr_node->value;
  }
  return -1;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {

  for (int i = 0; i < numsSize; i++) {
    int compliment = target - nums[i];
    int value = hash_find(compliment, nums);
    if (value != -1) { // check if compliment has been hashed
      int* ans = malloc(sizeof(int) * 2);
      ans[0] = i;
      ans[1] = value;
      *returnSize = 2;
      return ans; // return ans
    }
    hash_insert(nums[i], i);  // otherwise, hash curr and move on
  }
  *returnSize = 0;
  return NULL;
}