Solutions of "Two Sum" problem on LeetCode

Updated Apr 30, 2024#dsa#leetcode#hash-tables

The Two Sum problem is a popular coding interview question that asks you to find two numbers in an array that add up to a given target value. The problem statement typically provides an integer array nums and an integer target. You need to find two elements in the nums array such that their sum equals target and return their indices as an array.

For example, given an array nums = [2, 7, 11, 15] and a target value target = 9, the function should return [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

The problem can be solved using various algorithms such as brute force, two-pass hash table, one-pass hash table, or two pointers. The time and space complexity of the algorithm may vary based on the approach used.

Solution Implementation Time Space
Brute force Iterate through each element x and find if there is another value that equals target - x. O(n2) O(1)
Two-pass hash table In the first iteration, add each element’s value and its index to a hash table. In the second iteration, check if each element’s complement (target - nums[i]) exists in the hash table. O(n) O(n)
One-pass hash table While we iterate and insert elements into the hash table, we also look back to check if the current element’s complement already exists in the hash table. If it exists, we have found a solution and return the indices. O(n) O(n)
Two pointers Sort the array and use two pointers to scan through the array from both ends until they meet. O(nlogn) O(1)

The one-pass hash table solution is often preferred as it strikes a good balance between time complexity and space complexity, the logic is also straightforward and easy to understand. As soon as the required complement is found in the hash table, the solution can be returned immediately, making it very efficient for cases where the solution is located early in the array.

Here’s my one-pass hash table solution in different languages:


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

vector<int> twoSum(vector<int> &nums, int target) {
  unordered_map<int, int> map;
  for (int i = 0; i < nums.size(); i++) {
    int complement = target - nums[i];
    // Check if the complement is already in the hash map
    if (map.count(complement) > 0) {
      // If yes, return the indices of both elements
      return {map[complement], i};
    // Otherwise, store the current element and its index in the hash map
    map[nums[i]] = i;
  // If no solution is found, return an empty vector
  return {};


func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var numToIndex: [Int: Int] = [:]
    for (index, num) in nums.enumerated() {
        if let complementIndex = numToIndex[target - num] {
            return [complementIndex, index]
        numToIndex[num] = index
    return []


def two_sum(nums, target):
    num_to_index = {}
    for index, num in enumerate(nums):
        complement = target - num
        if complement in num_to_index:
            return [num_to_index[complement], index]
        num_to_index[num] = index
    return []


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