What i'm doing wrong using HashMap in C to resolve TwoSum problem? (-1 input)

Question

I'm currently studying C to learn more about data structures and algorithms (DSA) and their fundamentals.

Starting with LeetCode, the first problem is the "Two Sum."

I'm trying to solve it using a HashMap, but I can't understand why my code isn't working with the specific input:

[-10, -1, -18, -19] and target -19.

typedef struct {
    int key;
    int value;
} HashNode;

int hash (int key, int size){
    return abs(key) % size;
}

void insert (HashNode *hashTable, int size, int key, int value){
    int index = hash(key, size);
    while (hashTable[index].key != -1){
        index = (index + 1) % size;
    }
    hashTable[index].key = key;
    hashTable[index].value = value;
}


int search (HashNode *hashTable, int size, int key){
    int index = hash(key, size);

    while (hashTable[index].key != -1){
        if (hashTable[index].key == key){
            return hashTable[index].value;
        }
        index = (index + 1) % size;
    }
    return -1;
}
int *twoSum (int *nums, int numsSize, int target, int *returnSize) {
    int hashSize = numsSize * 2;
    HashNode *hashTable = malloc(hashSize * sizeof(HashNode));

    int *result = (int*)malloc (2 * sizeof(int));
    *returnSize = 2;


    for (int i = 0; i < hashSize; i++){
        hashTable[i].key = -1;
    }

    for (int i = 0; i < numsSize; i++){
        int complement = target - nums[i];
        int foundIndex = search(hashTable, hashSize, complement);

        if (foundIndex  != -1){
            result[0] = foundIndex;
            result[1] = i;
            free(hashTable);

            return result;
        }
        insert(hashTable, hashSize, nums[i], i);
    }

    free(hashTable);

    return result;
}

What i'm i doing wrong?

Current output

I already tried to review the HashMap logic, mainly the search function which uses (-1) as part of the true/false concept, but I don't know how to deal with this.

I tried to use AI for review, but it wasn't useful. I searched around the web, but my hashMap function seems a bit different from the others.

Answer 1

You are checking that the key is not -1 to determine whether or not there is actually an entry at a particular index, but this is not correct as -1 is a possible value in the array. The constraints state that the magnitude of each array element is at most 10⁹, so you could use INT_MIN as the sentinel instead.

#include <limits.h>
// ...
while (hashTable[index].key != INT_MIN) {
    index = (index + 1) % size;
}
// etc