Core Concepts

Dynamic Array Allocation

To create a dynamic array in C, use malloc from stdlib.h:

int* arr = (int*)malloc(len * sizeof(int));

Reading Array Input with scanf

scanf automatically skips whitespace (spaces, tabs, newlines) when reading input. Use getchar() to clear the newline character left in the input buffer after reading integers to insure subsequent scanf calls work correctly.

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

int main() {
    int *data, length, i, target;
    printf("Enter array length: ");
    scanf("%d", &length);
    printf("Enter array elements: ");
    data = (int*)malloc(length * sizeof(int));
    for (i = 0; i < length; i++) {
        scanf("%d", data + i);
    }
    printf("Enter target number: ");
    getchar();
    scanf("%d", &target);
    for (i = 0; i < length; i++) {
        if (*(data + i) == target) {
            printf("Found at index %d", i);
            return 0;
        }
    }
    printf("Not found");
    return 0;
}

Determining Array Length in C

• strlen: Only works for char arrays with null termination.
• sizeof: Use sizeof(arr)/sizeof(arr[0]) to calculate the length of any array.

Problem Sloution: Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that sum to target.

Brute Force Approach

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* indices = (int*)malloc(2 * sizeof(int));
    if (indices == NULL) {
        return NULL;
    }
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[j] == target - nums[i]) {
                indices[0] = i;
                indices[1] = j;
                *returnSize = 2;
                return indices;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

Hash Table Implementation

A hash table stores key-value pairs where the storage location is determined by the key. For this problem, we use array values as keys and they indices as values.

Hash Function: (key + 1000000000) % size (offset ensures positive results)

Collision Resolution: Chaining (linked list at each bucket)

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

typedef struct HashNode {
    int key;
    int index;
    struct HashNode* next;
} HashNode;

// Create hash table
HashNode** initHashTable(int capacity) {
    HashNode** table = (HashNode**)malloc(capacity * sizeof(HashNode*));
    if (table == NULL) return NULL;
    for (int i = 0; i < capacity; i++) {
        table[i] = NULL;
    }
    return table;
}

// Hash function
int computeHash(int key, int capacity) {
    return (key + 1000000000) % capacity;
}

// Insert key-value pair
void hashInsert(HashNode** table, int key, int idx, int capacity) {
    int bucket = computeHash(key, capacity);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->key = key;
    node->index = idx;
    node->next = table[bucket];
    table[bucket] = node;
}

// Search for key
int hashSearch(HashNode** table, int key, int capacity) {
    int bucket = computeHash(key, capacity);
    HashNode* current = table[bucket];
    while (current != NULL) {
        if (current->key == key) {
            return current->index;
        }
        current = current->next;
    }
    return -1;
}

// Two Sum using hash table
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    if (result == NULL) {
        *returnSize = 0;
        return NULL;
    }
    
    HashNode** hashTable = initHashTable(numsSize);
    if (hashTable == NULL) {
        free(result);
        *returnSize = 0;
        return NULL;
    }
    
    // Build hash table
    for (int i = 0; i < numsSize; i++) {
        hashInsert(hashTable, nums[i], i, numsSize);
    }
    
    // Find complement
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int compIdx = hashSearch(hashTable, complement, numsSize);
        if (compIdx != -1 && compIdx != i) {
            result[0] = compIdx;
            result[1] = i;
            *returnSize = 2;
            // Cleanup
            free(hashTable);
            return result;
        }
    }
    
    free(hashTable);
    free(result);
    *returnSize = 0;
    return NULL;
}