The Two Sum problem is a fundamental algorithmic challenge often seen in technical interviews. It tests a developer’s ability to manipulate arrays and use efficient search techniques. In this post, we will solve the Two Sum problem in C, providing both a brute-force approach and an optimized solution using a hashmap (which we will emulate in C using structures).

Problem Statement

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

Constraints:

  1. You may assume that each input would have exactly one solution.
  2. You cannot use the same element twice.

Example:

Input: nums = {2, 7, 11, 15}, target = 9
Output: {0, 1}  // nums[0] + nums[1] = 2 + 7 = 9

Step-by-Step Solution

Step 1: Brute-Force Approach

The brute-force solution involves checking every possible pair of numbers in the array to find two numbers whose sum equals the target. This is easy to implement but inefficient for large arrays.

Approach:

  1. Iterate through each element in the array.
  2. For each element, iterate through the rest of the array to check if their sum equals the target.
  3. If a valid pair is found, return their indices.

C Code (Brute Force):

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

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = i;
                result[1] = j;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL;  // Return NULL if no solution is found (this won't happen if one solution is guaranteed)
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);
    
    if (result != NULL) {
        printf("Indices: [%d, %d]\n", result[0], result[1]);  // Output: [0, 1]
        free(result);  // Don't forget to free the allocated memory
    } else {
        printf("No two sum solution found.\n");
    }
    return 0;
}

Explanation:

  • We use a nested loop to check all possible pairs of elements in the array.
  • When a pair that sums to the target is found, we allocate memory to store the indices and return the result.
  • If no pair is found, the function returns NULL.

Time Complexity:

  • Time Complexity: O(n^2) — We compare each element with every other element in the array, which leads to quadratic time complexity.

Step 2: Optimized Approach Using a Hashmap

Since C does not have built-in support for hashmaps like Python or Java, we will emulate a hashmap using arrays and a hash function. The hashmap will allow us to store the indices of elements we've seen so far and look up complements in constant time.

Hashmap Emulation in C

We'll create a simple structure to store key-value pairs (where the key is the number and the value is the index). We can use a fixed-size array (hashmap) and handle collisions by linear probing.

Approach:

  1. Create a hashmap to store each number and its index as we iterate through the array.
  2. For each element, calculate its complement (target - current number).
  3. Check if the complement exists in the hashmap. If it does, return the indices.
  4. If not, store the current number and its index in the hashmap.

C Code (Optimized Solution):

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

#define HASHMAP_SIZE 10000  // A large enough size to minimize collisions

// Hashmap node
typedef struct {
    int key;  // The number
    int value;  // The index of the number in the array
} HashNode;

// Simple hash function (modular hashing)
int hash(int key) {
    return abs(key) % HASHMAP_SIZE;
}

// Function to find two sum
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    HashNode* hashmap = (HashNode*)calloc(HASHMAP_SIZE, sizeof(HashNode));
    
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int hashIndex = hash(complement);
        
        // Linear probing to find complement
        while (hashmap[hashIndex].key != 0) {
            if (hashmap[hashIndex].key == complement) {
                int* result = (int*)malloc(2 * sizeof(int));
                result[0] = hashmap[hashIndex].value;
                result[1] = i;
                *returnSize = 2;
                free(hashmap);
                return result;
            }
            hashIndex = (hashIndex + 1) % HASHMAP_SIZE;  // Handle collision
        }
        
        // Insert the current number and its index into the hashmap
        hashIndex = hash(nums[i]);
        while (hashmap[hashIndex].key != 0) {
            hashIndex = (hashIndex + 1) % HASHMAP_SIZE;  // Handle collision
        }
        hashmap[hashIndex].key = nums[i];
        hashmap[hashIndex].value = i;
    }
    
    free(hashmap);
    *returnSize = 0;
    return NULL;  // No solution found
}

int main() {
    int nums[] = {2, 7, 11, 15};
    int target = 9;
    int returnSize;
    int* result = twoSum(nums, 4, target, &returnSize);
    
    if (result != NULL) {
        printf("Indices: [%d, %d]\n", result[0], result[1]);  // Output: [0, 1]
        free(result);
    } else {
        printf("No two sum solution found.\n");
    }
    return 0;
}

Explanation:

  • HashNode: This structure holds a key-value pair representing a number and its index in the array.
  • hash(): A simple hash function to map numbers to indices.
  • We use a fixed-size array (hashmap) to emulate a hashmap. Collisions are handled by linear probing, where we check the next slot in the array if the current one is occupied.
  • For each element, we calculate the complement and check if it exists in the hashmap.
  • If the complement is found, we return the indices. If not, we insert the current number and its index into the hashmap.

Time Complexity:

  • Time Complexity: O(n) — We pass through the array once, and lookups in the hashmap take constant time (in the average case).
  • Space Complexity: O(n) — The hashmap stores up to n elements.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    int nums[] = {-3, 4, 3, 90};
int target = 0;
int* result = twoSum(nums, 4, target);
printf("%d, %d\n", result[0], result[1]);  // Output: 0, 2

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    int nums[] = {3, 3};
int target = 6;
int* result = twoSum(nums, 2, target);
printf("%d, %d\n", result[0], result[1]);  // Output: 0, 1

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    int nums[] = {1, 4};
int target = 5;
int* result = twoSum(nums, 2, target);
printf("%d, %d\n", result[0], result[1]);  // Output: 0, 1

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    int nums[] = {0, 4, 3, 0};
int target = 0;
int* result = twoSum(nums, 4, target);
printf("%d, %d\n", result[0], result[1]);  // Output: 0, 3

  5. Large Inputs:
    If the array contains a large number of elements, the hash table approach ensures efficiency even with significant data size.

    int nums[100000];
for (int i = 0; i < 100000; i++) {
    nums[i] = i;
}
int target = 199999;
int* result = twoSum(nums, 100000, target);
printf("%d, %d\n", result[0], result[1]);  // Output: 99999, 99998

Conclusion

The Two Sum problem can be solved efficiently using a hashmap, which allows for constant time lookups. In C, we can emulate a hashmap using a structure and handle collisions through linear probing. By optimizing from a brute-force solution with O(n^2) time complexity to a hashmap-based solution with O(n) time complexity, we significantly improve performance, especially for large input sizes.

Understanding how to implement these solutions in a low-level language like C gives you better insight into memory management and algorithm optimization.