Coding Problem : Two Sum

Problem Name: Two Sum

Problem Statement:
Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Input:
An array of integers `nums` (1 ≤ nums.length ≤ 10^4, -10^9 ≤ nums[i] ≤ 10^9).
An integer `target` (-10^9 ≤ target ≤ 10^9).

Output:
Indices of the two numbers such that they add up to `target`.

Constraints:
Only one valid answer exists.
Each element in the array is unique.

Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Platforms:

• LeetCode
• GeeksforGeeks

Companies:

• Google
• Microsoft

Topics Covered:
Hash Tables, Array

Solution:

Algorithm:
1. Create a hash table to store the complement of each number.
2. Iterate through the array.
3. For each number, check if its complement exists in the hash table.
4. If found, return the indices.
5. Otherwise, add the number and its index to the hash table.

Code Implementation:

C:

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

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* result = (int*)malloc(2 * 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;
                *returnSize = 2;
                return result;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}
                

C++:

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int> numMap;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (numMap.find(complement) != numMap.end()) {
            return {numMap[complement], i};
        }
        numMap[nums[i]] = i;
    }
    return {};
}
                

Java:

import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<integer > map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
                

Python:

from typing import List

class Solution:
    def two_sum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i
        return []
                

Complexity Analysis:

Case	Time Complexity	Space Complexity
Worst Case	O(n)	O(n)
Average Case	O(n)	O(n)
Best Case	O(1)	O(n)