Solving the "Two-Sum" Problem

Apr 03, 2023#dsa#leetcode

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 numsnums and an integer targettarget. You need to find two elements in the nums array such that their sum equals targettarget and return their indices as an array.

For example, given an array nums=[2,7,11,15]nums = [2, 7, 11, 15] and a target value target=9target = 9, the function should return [0,1][0, 1] because nums[0]+nums[1]=2+7=9nums[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)O(n), where nn 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.