1. Two Sum

INFO

Problem: Two Sum

Pattern: Hash map / complement lookup

Two Sum asks us to find two different indexes whose values add up to a target. A brute-force approach checks every pair, but that repeats work and becomes slow as the input grows.

The useful observation is that when we are reading one number, we already know the exact number that would complete the pair. If the current value is v, the missing value is target - v. A dictionary can remember numbers we have already seen and the index where each number appeared.

Approach

Create a dictionary where the key is a number from the array and the value is its index. Then scan the array once:

1. Compute the complement for the current value.
2. Check whether that complement already exists in the dictionary.
3. If it exists, return the stored index and the current index.
4. If it does not exist, store the current value and continue.

This order is important. We check before inserting the current value so the same element is not accidentally used twice.

Swift Notes

Swift dictionaries make this solution clean because dictionary lookup returns an optional. If numCount[remainingValue] has a value, we found a valid earlier index. Otherwise, the result is nil, and we store the current value.

The solution below keeps the same structure you can use in an interview: one loop, one dictionary, and an immediate answer when a complement is found.

Complexity

• Time complexity: O(n) because each number is processed once.
• Space complexity: O(n) because the dictionary can store up to all numbers.

Edge Cases

• The pair may include duplicate values, such as [3, 3] with target 6.
• The answer can appear at the beginning, middle, or end of the array.
• Negative numbers work because complement lookup does not depend on ordering.

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var numCount: [Int: Int] = [:]
        var result: [Int] = []
        for (i, v) in nums.enumerated() {
            let remainingValue = target - v
            if let index = numCount[remainingValue] {
                result = [index , i]
            } else {
                numCount[v] = i
            }
        }
        return result
    }
}

var solution = Solution()

var testcase1 = solution.twoSum([2,7,11,15], 9)
print(testcase1) // [0, 1]

var testcase2 = solution.twoSum([3,2,4], 6)
print(testcase2) // [1, 2]

var testcase3 = solution.twoSum([3,3], 6)
print(testcase3) // [0, 1]