Solving the ‘Two Sum Problem’ on LeetCode — C Solutions Walkthrough

Image Source

Introduction

In this post, we will explore three diverse solutions to the Two Sum Problem in C, evaluating their time and space complexity to aid in understanding the most optimal approach. A detailed, step-by-step explanation with commented code for each solution is provided to offer deeper insights and clarity after the conclusion.

Problem Description

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

Function Prototype:

int* twoSum(int* nums, int numsSize, int target, int* returnSize);

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution 1: Brute Force Approach

Explanation

In this approach, we use two loops to compare each pair of numbers to find the two numbers that add up to the target sum. We iterate through the array with two loops, comparing every pair of numbers to find if they add up to the target value.

C Code:

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

Time Complexity: O(n²), For each element, we try to find its complement by looping through the rest of the array. Both loops run n times in the worst case, making the time complexity O(n²).

Space Complexity: O(1), There is no extra space used; the output is stored in the passed array (returnSize).

Solution 2: Sorting and Two Pointers Approach

Explanation

In this approach, we use two pointers technique after sorting the array. Please note that since we are sorting the array, the original indices will be lost. To keep track of indices, you can create a structure to store both number and its index.

C Code:

typedef struct {
    int num;
    int index;
} Number;

int compare(const void* a, const void* b) {
    return ((Number*)a)->num - ((Number*)b)->num;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    Number numbers[numsSize];
    for(int i = 0; i < numsSize; i++) {
        numbers[i].num = nums[i];
        numbers[i].index = i;
    }
    qsort(numbers, numsSize, sizeof(Number), compare);

    int left = 0, right = numsSize - 1;
    while(left < right) {
        int sum = numbers[left].num + numbers[right].num;
        if(sum == target) {
            *returnSize = 2;
            int* result = (int*)malloc(*returnSize * sizeof(int));
            result[0] = numbers[left].index;
            result[1] = numbers[right].index;
            return result;
        } else if(sum < target) {
            left++;
        } else {
            right--;
        }
    }
    *returnSize = 0;
    return NULL;
}

Time Complexity: O(nlogn), The sorting of the array takes O(nlogn) time, and then the array is traversed once which takes O(n) time, thus the overall time complexity is O(nlogn).

Space Complexity: O(n), Other than the initial array, no extra space is needed (not considering space used by sorting algorithm).

Solution 3: Optimized Pointer Approach

Explanation

In this approach, we optimize the search process by using the pointer approach. The pointers will help to efficiently find the complementary number.

C Code:

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* map = (int*)malloc((target + 1) * sizeof(int));
    for(int i = 0; i <= target; i++) map[i] = -1;

    for(int i = 0; i < numsSize; i++) {
        if(nums[i] <= target) {
            int complement = target - nums[i];
            if(map[complement] != -1) {
                *returnSize = 2;
                int* result = (int*)malloc(*returnSize * sizeof(int));
                result[0] = map[complement];
                result[1] = i;
                free(map);
                return result;
            }
            map[nums[i]] = i;
        }
    }
    *returnSize = 0;
    free(map);
    return NULL;
}

Time Complexity: O(n), The array is traversed once, and for each element, it checks whether its complement is in the hash map, which takes O(1) time on average.

Space Complexity: O(n), A hash map is used to store the elements of the array along with their indices. The space required for the hash map grows linearly with the number of elements in the array, resulting in a space complexity of O(n).

Conclusion and Comparison

This exploration into the Two Sum problem in C showcases the diversity of approaches available, each with its own set of strengths and drawbacks:

Brute Force Approach:

• Pros: Simple and straightforward to implement.
• Cons: Highly inefficient for large datasets due to its O(n²) time complexity and O(1) space complexity.

Sorting and Two Pointers Approach:

• Pros: More time-efficient than the brute force approach with a time complexity of O(nlogn).
• Cons: Loss of original indices (can be handled with additional space), and O(n) space complexity.

Optimized Pointer Approach:

• Pros: Offers the best time complexity of O(n) for larger datasets, allowing for efficient processing.
• Cons: Uses additional space with O(n) space complexity and involves slightly more complexity in implementation.

Final Thoughts

Choosing between these approaches should encompass a meticulous evaluation of the dataset size and the acceptable trade-offs between time and space complexity.

The Optimized Pointer Approach often stands out as the most sensible and efficient solution, maintaining a healthy equilibrium between time complexity, space usage, and implementation complexity. While it uses additional space, the considerable enhancement in time efficiency makes it a worthwhile choice for larger datasets.

1. Two Sum — LeetCode
2. Time Complexity — GeeksforGeeks
3. Space Complexity — GeeksforGeeks
4. Two Pointers Technique — GeeksforGeeks

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

Solution 1: Brute Force Approach with Comments

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    
    // Step 1: Start the first loop to iterate over the array elements.
    for(int i = 0; i < numsSize; i++) {
        // Step 2: Start the second loop to iterate over the rest of the array elements.
        for(int j = i + 1; j < numsSize; j++) {
            // Step 3: Check if the numbers at current indices i and j add up to the target.
            if(nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    // Step 4: If no such indices found, return NULL and set returnSize to 0.
    *returnSize = 0;
    return NULL;
}

• Step 1: The outer loop iterates over each number in the array.
• Step 2: The inner loop iterates over the rest of the numbers for each number from the outer loop.
• Step 3: If a pair sums up to the target, their indices are stored in the result array and the array is returned.
• Step 4: If no such pair is found, returnSize is set to 0 and NULL is returned.

Solution 2: Sorting and Two Pointers Approach with Comments

typedef struct {
    int num;
    int index;
} Number;

int compare(const void* a, const void* b) {
    return ((Number*)a)->num - ((Number*)b)->num;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    Number numbers[numsSize];
    // Step 1: Map numbers to their original indices.
    for(int i = 0; i < numsSize; i++) {
        numbers[i].num = nums[i];
        numbers[i].index = i;
    }
    // Step 2: Sort the array of numbers.
    qsort(numbers, numsSize, sizeof(Number), compare);
    int left = 0, right = numsSize - 1;
    
    // Step 3: Use two pointers to find the target sum.
    while(left < right) {
        int sum = numbers[left].num + numbers[right].num;
        // If the sum is equal to the target, return the indices.
        if(sum == target) {
            *returnSize = 2;
            int* result = (int*)malloc(*returnSize * sizeof(int));
            result[0] = numbers[left].index;
            result[1] = numbers[right].index;
            return result;
        } else if(sum < target) {
            left++;
        } else {
            right--;
        }
    }
    // Step 4: If no such indices found, return NULL and set returnSize to 0.
    *returnSize = 0;
    return NULL;
}

• Step 1: Map numbers to their original indices.
• Step 2: Sort the array of numbers.
• Step 3: Use two pointers to find the target sum.
• Step 4: If no such pair is found, returnSize is set to 0 and NULL is returned.

Solution 3: Optimized Hash Map Approach with Comments

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int* map = (int*)malloc((target + 1) * sizeof(int));
    // Step 1: Initialize the map with -1.
    for(int i = 0; i <= target; i++) map[i] = -1;

    // Step 2: Iterate through the array.
    for(int i = 0; i < numsSize; i++) {
        if(nums[i] <= target) {
            int complement = target - nums[i];
            // Step 3: If complement is found in map, return the indices.
            if(map[complement] != -1) {
                *returnSize = 2;
                int* result = (int*)malloc(*returnSize * sizeof(int));
                result[0] = map[complement];
                result[1] = i;
                free(map);
                return result;
            }
            // Step 4: Otherwise, update the map.
            map[nums[i]] = i;
        }
    }
    // Step 5: If no such indices found, return NULL and set returnSize to 0.
    *returnSize = 0;
    free(map);
    return NULL;
}

• Step 1: Initialize the map with -1.
• Step 2: Iterate through the array.
• Step 3: If complement is found in map, return the indices.
• Step 4: Otherwise, update the map with the current number and its index.
• Step 5: If no such pair is found, returnSize is set to 0 and NULL is returned