5
\$\begingroup\$

I came across a problem on LeetCode. There is an input array of integers. I need to find out if there any repeating integers, then return true else false. So, I tried using a hashtable library available in C and wrote the code below. My run time is approximately 44ms.

  1. How can I optimize this code?
  2. Using hashtable, can I improve the logic further?
struct hash {
    int key;
    int value;
    UT_hash_handle hh;
};

struct hash *hashtable = NULL;

void addToHash(int key, int value)
{
  struct hash *map;
  //I am using the array elements as hash keys
  HASH_FIND_INT(hashtable, &key, map);

  if(map == NULL)
  {
    map = (struct hash*)malloc(sizeof(struct hash));
    map->key = key;
    HASH_ADD_INT(hashtable, key, map);
  }     
  map->value = value;
}   

struct hash *findInHash(int key)
{
    struct hash *h;
    HASH_FIND_INT(hashtable, &key, h);
    return h;
}

bool containsDuplicate(int* nums, int numsSize) {

    struct hash *hPtr;
    int target = 0;
    hashtable = NULL;
    if((numsSize <= 1) || (nums == 0)) return false;

    int i, index1 = 0;   

    for(i = 0; i < numsSize; i++)
    {
        /*The below statement will look if the key is already present in the 
          hashtable*/
        hPtr = findInHash(*(nums + i) - target);
        /*If the key is found already, then it look for the value of that 
        key. If the value and the current array element is same, then a 
        duplicate exist*/
        if(hPtr && hPtr->key == *(nums+i))
           return true;
        addToHash(*(nums + i), i);
    }
    struct hash *temp;
    HASH_ITER(hh, hashtable, hPtr, temp) {free(hPtr);}
    return false;
}
\$\endgroup\$

closed as off-topic by Toby Speight, pacmaninbw, yuri, Mast, Edward Jun 5 at 17:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – Toby Speight, pacmaninbw, yuri, Edward
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    \$\begingroup\$ "How can I optimize this code?" be specific. optimize for speed, memory usage, code footprint, clarity, ...? \$\endgroup\$ – chux Jun 1 at 18:57
  • 1
    \$\begingroup\$ I'm assuming HASH_FIND_INT, HASH_ITER are library calls. But did you copy and paste the entire library source code into the Leetcode text input? Surely, this is bringing a gun to a knife fight. There are numerous qsort solutions that run 12ms with just a few lines of code. I don't think Leetcode runs enough tests for speed to matter on this challenge. Also, if you're using someone's library as a client, you're pretty much tied down to their implementation. More clarification about what you're trying to achieve would be helpful here. \$\endgroup\$ – ggorlen Jun 2 at 6:09
  • 1
    \$\begingroup\$ How does this teach you about hash tables? You loaded the library, called their functions and it works--there's no hashing algorithm here. All of the potential for optimization is in the library code that's not included in this post. \$\endgroup\$ – ggorlen Jun 2 at 23:49
  • 1
    \$\begingroup\$ As @ggorlen mentioned a hash table will be overkill for this solution. Since a hash table will involve allocating small bits of memory many times it is also not going to perform as well as something using an array possibly created by calloc() once. Each time the algorithm adds a node it will call a system routine to allocate the memory to the process, that means the program itself will be swapped out while the memory is being allocated. \$\endgroup\$ – pacmaninbw Jun 3 at 14:10
  • 4
    \$\begingroup\$ You can improve this question by including the description of the problem statement from LeetCode and including the hash table functions, currently there isn't enough code here to review. \$\endgroup\$ – pacmaninbw Jun 3 at 14:13