Solving the "Two-Sum" Problem

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, or one-pass hash table. The time and space complexity of the algorithm may vary based on the approach used.

Here’s a solution in Swift:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
  var numDict = [Int: Int]()

  for (i, num) in nums.enumerated() {
    let complement = target - num

    if let complementIndex = numDict[complement] {
      return [complementIndex, i]
    }

    numDict[num] = i
  }

  fatalError("No two sum solution")
}

let nums = [2, 7, 11, 15]
let target = 18
print(twoSum(nums, target))  // [1, 2]

The time complexity of the above solution to the Two Sum problem is $O(n)$, where $n$ is the length of the input array nums. This is because the algorithm performs a single pass through the array, and for each element in the array, it performs a constant-time dictionary lookup operation to check if the complement of the current element exists in the dictionary.