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.

Two Sum - LeetCode

Approach

  1. sum = a + b \(\implies\) b = sum - a, where a is the current element.
  2. Create a hash map to store b as key and index of a as value.
  3. Iterate over the array in each iteration check if the current element is present in the hash map. If found, the index of it’s counterpart is already stored in the hash map.
  4. Else, store b and the current index in the hash map.

Solution in Swift

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {

        var dict: [Int: Int] = [Int: Int]()

        for (index, number) in nums.enumerated() {
            if let firstPartIndex: Int = dict[number] {
                return [firstPartIndex, index]
            }
            dict[target - number] = index
        }

        return []
    }
}

Complexity

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(n)\)