Building HashMap from Scratch in C for Sum Of Two Problem Solving on LeetCode
Experiments with implementing a set in C for solving a common problem from LeetCode — inspired me, and I decided to play around with solving another LeetCode problem in C.
My next experiment is solving the problem of finding the sum of two array elements.
The task looks as simple as the previous one.
Given an array of integer nums and an integer target, return the indices of the two numbers so that they add up to the target.
The solution by simple enumeration is not very efficient and uninteresting from the point of view of studying data structures.
Solutions using a hash table look more efficient and exciting.
The algorithm is the following:
- I create a hash table in which the key is a numeric value from the array, and the corresponding value is an index.
- I am going through the array.
- Check if a number equals one of the complements stored in the hash table.
- If yes a solution is found, we return the index of the current element and the index of the element found in the hash table.
- If not, add the current value and index to the hash table and continue the loop.
The C++ implementation looks something like this:
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class SumOfTwoSolver
{
public:
static vector<int> getIndexes( vector<int>& nums, int target )
{
vector<int> result;
int numsSize = nums.size();
unordered_map<int, int> complementMap;
for ( size_t index = 0; index < numsSize; index++ )
{
int complement = target - nums[ index ];
if ( complementMap.count( complement ) )
{
result.push_back( index );
result.push_back( complementMap[ complement ] );
return result;
}
complementMap[ nums[ index ] ] = index;
}
return result;
}
static void showResult( vector<int> result )
{
if ( result.size() > 0 )
{
cout << "result: [ " << result[ 0 ] << ", " << result[ 1 ] << " ]" << endl;
}
else
{
cout << "result: []" << endl;
}
}
};
int main()
{
vector<int> nums{ 2, 7, 11, 15 };
int target = 9;
vector<int> result = SumOfTwoSolver::getIndexes( nums , target );
SumOfTwoSolver::showResult( result );
nums = { 3, 2, 4 };
target = 6;
result = SumOfTwoSolver::getIndexes( nums , target );
SumOfTwoSolver::showResult( result );
nums = { 3, 2, 4 };
target = 11;
result = SumOfTwoSolver::getIndexes( nums , target );
SumOfTwoSolver::showResult( result );
cout << "End of programm." << endl;
return EXIT_SUCCESS;
}Output example:
result: [ 1, 0 ]
result: [ 2, 1 ]
result: []
End of programm.How can this be done in C?
First, I modify the set implementation to a hash table implementation.
I follow the path of least resistance and have added one more field to the Node structure to store the key and the value. Also, I have modified the Map_add function corresponding to the new Node’s field.
typedef struct Node
{
int key;
int value;
struct Node * next;
} Node;
typedef struct Map
{
int size;
Node ** table;
} Map;
Map * Map_create( size_t size )
{
Map * map = (Map*) malloc( sizeof( Map ) );
map->size = 0;
map->table = ( Node** ) calloc( size, sizeof( Node* ) );
return map;
}
void Map_destroy( Map * map, size_t size )
{
for ( size_t index = 0; index < size; index++ )
{
Node * node = map->table[ index ];
while ( node != NULL )
{
Node * temp = node;
node = node->next;
free( temp );
}
}
free( map->table );
free( map );
}
unsigned int hash( int key, size_t size )
{
return key % size;
}
Node * findNode( Node * node, int key )
{
while ( node != NULL )
{
if ( node->key == key )
{
return node;
}
node = node->next;
}
return NULL;
}
void Map_add( Map * map, int key, int value, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
if ( node == NULL)
{
node = (Node*) malloc( sizeof( Node ) );
node->key = key;
node->value = value;
node->next = map->table[ index ];
map->table[ index ] = node;
map->size++;
}
}
bool Map_contains( Map * map, int key, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
return ( node != NULL );
}I also have added a function that will return a value by key
By slightly modifying the function to check for the existence of a key from the previous example.
int Map_get( Map * map, int key, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
if ( node != NULL ) return node->value;
return INT_ERROR_CODE;
}The function for searching indices looks like a C++ implementation.
int * sunOfTwoSolver( int * nums, int numsSize, int target, int * returnSize )
{
Map * complementMap = Map_create( numsSize );
for ( size_t index = 0; index < numsSize; index++ )
{
int complement = target - nums[ index ];
if ( Map_contains( complementMap, complement, numsSize ) )
{
int * result = malloc( 2 * sizeof( int ) );
*returnSize = 2;
result[ 0 ] = index;
result[ 1 ] = Map_get( complementMap, complement, numsSize );
Map_destroy( complementMap, numsSize );
return result;
}
Map_add( complementMap, nums[ index ], index, numsSize );
}
Map_destroy( complementMap, numsSize );
return NULL;
}The complete solution looks like this.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define INT_ERROR_CODE -555
typedef struct Node
{
int key;
int value;
struct Node * next;
} Node;
typedef struct Map
{
int size;
Node ** table;
} Map;
Map * Map_create( size_t size )
{
Map * map = (Map*) malloc( sizeof( Map ) );
map->size = 0;
map->table = ( Node** ) calloc( size, sizeof( Node* ) );
return map;
}
void Map_destroy( Map * map, size_t size )
{
for ( size_t index = 0; index < size; index++ )
{
Node * node = map->table[ index ];
while ( node != NULL )
{
Node * temp = node;
node = node->next;
free( temp );
}
}
free( map->table );
free( map );
}
unsigned int hash( int key, size_t size )
{
return key % size;
}
Node * findNode( Node * node, int key )
{
while ( node != NULL )
{
if ( node->key == key )
{
return node;
}
node = node->next;
}
return NULL;
}
void Map_add( Map * map, int key, int value, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
if ( node == NULL)
{
node = (Node*) malloc( sizeof( Node ) );
node->key = key;
node->value = value;
node->next = map->table[ index ];
map->table[ index ] = node;
map->size++;
}
}
bool Map_contains( Map * map, int key, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
return ( node != NULL );
}
int Map_get( Map * map, int key, size_t size )
{
unsigned int index = hash( key, size );
Node * node = findNode( map->table[ index ], key );
if ( node != NULL ) return node->value;
return INT_ERROR_CODE;
}
int * sunOfTwoSolver( int * nums, int numsSize, int target, int * returnSize )
{
Map * complementMap = Map_create( numsSize );
for ( size_t index = 0; index < numsSize; index++ )
{
int complement = target - nums[ index ];
if ( Map_contains( complementMap, complement, numsSize ) )
{
int * result = malloc( 2 * sizeof( int ) );
*returnSize = 2;
result[ 0 ] = index;
result[ 1 ] = Map_get( complementMap, complement, numsSize );
Map_destroy( complementMap, numsSize );
return result;
}
Map_add( complementMap, nums[ index ], index, numsSize );
}
Map_destroy( complementMap, numsSize );
return NULL;
}
void printResult( int * result )
{
if ( result )
{
printf( "Result: [ %d, %d ]\n", result[ 0 ], result[ 1 ] );
}
else
{
puts( "Result: []" );
}
}
int main( void )
{
int nums[] = { 2, 7, 11, 15 };
int target = 9;
int numsSize = 4;
int * returnSize;
int * result = sunOfTwoSolver( nums, numsSize, target, returnSize );
printResult( result );
int nums_2[] = { 3, 2, 4 };
target = 6;
numsSize = 3;
result = sunOfTwoSolver( nums_2, numsSize, target, returnSize );
printResult( result );
target = 11;
result = sunOfTwoSolver( nums_2, numsSize, target, returnSize );
printResult( result );
puts( "End of program." );
return EXIT_SUCCESS;
}Result: [ 1, 0 ]
Result: [ 2, 1 ]
Result: []The solution involved implementing a truncated version of the set, which was used to create a hash table that can be recognized as an ADT. However, this article does not cover the details of implementing the ADT.
In daily practice, it is unlikely that you will have to implement sets and hash tables from 0.
Modern programming languages include these data structures in their standard libraries, which are well-optimized and thoroughly tested. Therefore, it is recommended to use only them in production code.
But implementing these structures on your own allows you to remember the basics, train your brain a little and enjoy the process.
