Two Sum

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

                                            
def twoSum(nums, target):
    memo = {}
    for i in range(len(nums)):

        need = target - nums[i]
        if need in memo:
            return [i, memo[need]]

        memo[nums[i]] = i

                                            
const twoSum = function(nums, t, m={}) {
    for(let i = 0; i < nums.length; i++){
        const need = t - nums[i];
        if(need in m ) return [i, m[need]];
        m[nums[i]] = i;
    }
};

                                            
func twoSum(nums []int, target int) []int {
	memo := make(map[int]int)
	for i, num := range nums {
		if val, is := memo[target-num]; is {
			return []int{i, val}
		}
		memo[num] = i
	}
	return []int{}
}

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

                                            
class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int: Int]()
        for (i, num) in nums.enumerated() {
            if let j = dict[target - num] {
                return [j, i]
            }
            dict[num] = i
        }
        return []
    }
}

                                            
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    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;
                return result;
            }
        }
    }
    return result; // control never reaches here since there is always exactly one solution
}

                                            
public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> seenNumbers = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (seenNumbers.ContainsKey(complement)) {
                return new [] { seenNumbers[complement], i };
            }
            if (!seenNumbers.ContainsKey(nums[i])) {
                seenNumbers.Add(nums[i], i);
            }
        }
        return new int[0]; // Should never be reached as there is exactly one solution
    }
}

                                            
function twoSum(nums: number[], target: number): number[] {
    const map: {[key: number]: number} = {};
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map[complement] !== undefined) {
            return [map[complement], i];
        }
        map[nums[i]] = i;
    }
    return [];
}

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $map = [];

        for ($i = 0; $i < count($nums); $i++) {
            $complement = $target - $nums[$i];
            if (array_key_exists($complement, $map)) {
                return [$map[$complement], $i];
            }
            $map[$nums[$i]] = $i;
        }

        return [];
    }
}

                                            
class Solution {
    fun twoSum(nums: IntArray, target: Int): IntArray {
        val map = mutableMapOf<Int, Int>()
        for ((index, value) in nums.withIndex()) {
            val complement = target - value
            if (map.containsKey(complement)) {
                return intArrayOf(map[complement]!!, index)
            }
            map[value] = index
        }
        return intArrayOf()
    }
}

                                            
class Solution {
  List<int> twoSum(List<int> nums, int target) {
    Map<int, int> numMap = {};
    for (int i = 0; i < nums.length; i++) {
      int complement = target - nums[i];
      if (numMap.containsKey(complement)) {
        return [numMap[complement]!, i];
      }
      numMap[nums[i]] = i;
    }
    return [];
  }
}

                                            
def two_sum(nums, target)
    hash = {}
    nums.each_with_index do |num, i|
        diff = target - num
        return [hash[diff], i] if hash.has_key?(diff)
        hash[num] = i
    end
end

                                            
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let mut map = HashMap::new();
        for (index, &num) in nums.iter().enumerate() {
            if let Some(&i) = map.get(&(target - num)) {
                return vec![i as i32, index as i32];
            }
            map.insert(num, index);
        }
        vec![]
    }
}

                                            
(define (two-sum nums target)
  (define (find-indices hmap index)
    (if (= index (length nums))
        '()
        (let* ((current-num (list-ref nums index))
               (complement (- target current-num)))
          (if (hash-has-key? hmap complement)
              (list (hash-ref hmap complement) index)
              (find-indices (hash-set hmap current-num index) (+ index 1))))))
  (find-indices (make-immutable-hash) 0))

                                            
two_sum(Nums, Target) ->
    two_sum(Nums, Target, dict:new(), 0).

two_sum([H|T], Target, Dict, Index) ->
    case dict:find(Target - H, Dict) of
        {ok, Idx} -> [Idx, Index];
        error -> two_sum(T, Target, dict:store(H, Index, Dict), Index + 1)
    end.

To solve this coding challenge, we want to find two indices in the array

nums

such that their corresponding elements add up to the given

target

. We will use a hash table (dictionary) to achieve this in an optimal way, aiming for a time complexity of O(n).

Explanation

Understanding the Problem : We are given an array of integers
nums

and an integer
target

. The task is to find two indices in
nums

such that the sum of the elements at these indices equals
target

. We must assume the input has exactly one solution, and an element cannot be used twice.
Naive Approach : The naive approach involves using two nested loops to check all pairs of elements and finding the ones that sum up to
target

. This leads to a time complexity of O(n^2).
Optimal Approach : A more efficient method uses a hash table (dictionary). By iterating through the array once while keeping track of the elements we've seen and their indices in the hash table, we can reduce the time complexity to O(n). This approach works by:

Checking if the complement of the current element (i.e.,
target - current element

) has already been seen.
If it has been seen, the current element and the seen element sum to
target

, and their indices are returned.
If it hasn’t been seen, the current element and its index are added to the hash table.

Hash Table Utilization : A hash table allows O(1) average-time complexity for both insert and lookup operations. This is why our optimal approach is efficient.

Detailed Steps in Pseudocode

Initialize an empty hash table to store elements and their indices.
Loop through each element in the array:

Calculate the complement by subtracting the current element from the target.
Check if the complement is already in the hash table.
If it is, return the current index and the index of the complement from the hash table.
If it isn’t, add the current element and its index to the hash table.

The function should return the indices found if they satisfy the requirements.

Pseudocode

                                            
Algorithm twoSum(nums, target):
# Initialize an empty hash table to store element values and their indices
seen_elements_indices = {}

# Iterate through each element in the array(nums) using its index
for current_index from 0 to length of nums - 1:

# Calculate the complement such that current_element + complement = target
current_element = nums[current_index]
complement = target - current_element

# Check if the complement exists in the hash table
if complement is in seen_elements_indices:
# If it exists, complement found, so return the indices of current element and complement
return [current_index, seen_elements_indices[complement]]

# If complement is not found, store the current element and its index in the hash table
seen_elements_indices[current_element] = current_index

# If the loop ends without returning, print a message
print("No solution found.")

Step-by-Step Explanation:

Initialization :

The variable

seen_elements_indices

is initialized as an empty dictionary. This dictionary will map the elements of

nums

to their respective indices.

Iteration :

Loop through the

nums

array with the index variable

current_index

Complement Calculation :

For each element at

current_index

, calculate its complement (

target - current_element

). This complement is the number that, when added to the current_element, would equal the target.

Hash Table Lookup :

Check if this complement exists in the hash table (

seen_elements_indices

). If it does, it means we have found two indices whose elements sum up to

target

Return Indices :

If the complement is found in the hash table, immediately return the list containing

current_index

and the stored index of the complement.

Store in Hash Table :

If the complement is not found, store the current element along with its index in the hash table for future reference.

This breakdown ensures we maintain an efficient O(n) time complexity for solving this challenge, as we only traverse the array once and perform O(1) operations for each element.