[LeetCode in Swift] Two Sum

Hello this is Derek! 👋

I’m starting a new blog series called LeetCode in Swift, where I solve LeetCode challenges in Swift, as I am in the middle of job hunting process and I need to prepare for possible upcoming coding interview.

This question is a Easy difficulty in LeetCode and shows history of being asked this question from interviews at Amazon, Adobe, Apple, Google, Microsoft, Yahoo, Spotify, Deloitte, Bloomberg, Uber, Accenture, and Capgemini for 0–6 months of experience interviewees. As you can see, it’s a really popular questions that are asked by many different companies.

Disclaimer: I am not an experienced developer nor I have a Computer Science education background. My solution may not be the most efficient or effective approach in solving the problem. The reason why I am writing this in blog series is to help these logics, algorithms and approach to stick into my head, and to possibly help absolute beginners who is also facing similar problems.

Today’s challenge: Two Sum

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.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Approach and Thought Process

To solve this problem efficiently, we need to carefully analyze the requirements and constraints. Let’s walk through our approach to the problem:

1. Element Pair Search: We need to find two elements in the array whose sum equals the target. Instead of checking all possible pairs of elements, which would result in a time complexity of O(n²), we can take advantage of a more efficient approach using a hash table.
2. Hash Table Usage: We can iterate over the array once, storing each element’s value and its index in a hash table. The key of each entry is the element’s value, and the value of each entry is the element’s index.
3. Finding the Matching Number: For each element, we need to find another number in the array that, when added to this element, equals the target. We call this number the “matching number”. You can think of it as the missing piece that completes the sum to reach the target. We calculate this matching number by subtracting the current element’s value from the target. If this matching number is found in our hash table, it means we have found the two numbers in the array that add up to the target.
4. Index Return: We return the indices of the two elements whose sum equals the target. If no indices are found, we can simply return negative values to show that there are no possibilities.

Now, let’s implement this solution.

Step 1. Initialize Hash Table

First, we initialize an empty hash table.

var emptyHash: [Int:Int] = [:]

Step 2. Iterate Over Array

Next, we iterate over the array. For each element, we calculate its complement and check if it is in the hash table.

for (index, num) in nums.enumerated() {
    let otherValue = target - num
}

Step 3. Check Complement in Hash Table

If the complement is in the hash table, we return the indices of the current element and the complement.

if let otherIndex = emptyHash[otherValue] {
    return [index, otherIndex]

Step 4. Store Element in Hash Table

If the complement is not in the hash table, we store the current element and its index in the hash table.

} else {
    emptyHash[num] = index
}

Step 5. Implementing the Solution

The complete solution looks like this:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        // Create an empty dictionary to store the numbers we've seen and their indices
        var emptyHash: [Int:Int] = [:]
        
        // Iterate over the array of numbers with their indices
        for (index, num) in nums.enumerated() {
            // Calculate the other value we need to reach the target
            let otherValue = target - num
            
            // If the other value is already in the dictionary, then we've found a solution
            if let otherIndex = emptyHash[otherValue] {
                // Return the current index and the index of the other value
                return [index, otherIndex]
            } else {
                // Otherwise, add the current number and its index to the dictionary
                emptyHash[num] = index
            }
        }
        
        // If we've gone through the entire array without finding a solution, return [-1, -1]
        return [-1, -1]
    }
}

Let’s try this code by actually showing a representation walk-through of the code to see what it looks like behind the scene. This should help us understand the solution better.

Example Test Case

nums = [3,2,4]
target = 6
emptyHash = [:]

Step 1:

When you enumerate nums array, nums array now has a dictionary format as following.

nums = [index=0:num=3, index=1:num=2, index=2:num=4]

Therefore, our first start of for loop we get:

index = 0
num = 3

otherValue = target - num = 6 - 3 = 3

At this point, emptyHash[3] does not exist, so we add num as a key and index as a value to the hash table:

emptyHash = [3:0]

Step 2:

index = 1
num = 2

otherValue = target - num = 6 - 2 = 4

Again, emptyHash[4] does not exist, so we add num as a key and index as a value to the hash table:

emptyHash = [3:0, 2:1]

Step 3:

index = 2
num = 4

otherValue = target - num = 6 - 4 = 2

Now, emptyHash[2] does exist, and it has the value 1. 
We've found a pair of numbers that sum to the target. 
The indices of these numbers are the current index and the value from the hash table:

indices = [1, 2]

So the solution for this test case is [1, 2]. Things are making a lot more sense right?

Let’s give it a go in LeetCode!

Our solution was accepted! Let’s evaluate our solution’s time and space complexity.

Time Complexity:

Iterating over the array once takes O(n) time, where n is the number of elements in the array.

Searching for and inserting elements into the hash table takes O(1) time on average, so the overall time complexity of our solution is O(n).

Space Complexity:

We use a hash table that can potentially store all elements in the array, so the space complexity of our solution is O(n), where n is the number of elements in the array.

That’s it! We have successfully solved the problem of finding two numbers that add up to a given target. It’s important to understand the thought process behind problem-solving as it helps us become better programmers and prepares us for coding interviews.

I hope you found this blog post helpful. If you have any suggestions or questions, please feel free to leave a comment. Stay tuned for more LeetCode challenges in Swift!

Happy coding, everyone! 🔥