Leetcode 1 — Two Sum

This post will cover the infamous Two Sum problem, an intro to coding challenges and example of the hash map data structure.

Problem Overview

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.

Contraints:

| 2 <= nums.length <= 10^4

| -10^9 <= nums[i] <= 10^9

| -10^9 <= target <= 10^9

Only one valid answer exists.

Okay, so this problem is concise, clear, and doesn’t leave us with many follow up questions. Some of my thoughts to begin with would be ensuring correct interpretation and expanding upon the constraints. So, let’s walk through some of my initial thoughts and notes:

1. A solution exists, therefore I don’t have any thoughts on what to return if a solution wasn’t found (though, in practice, maybe we should raise an error if that’s the appropriate path)
2. I can’t use the same element twice, BUT I can use the same number twice. Meaning, our return array MUST have 2 different indices.
3. Are there space or time complexity constraints?

Now, let’s run through some examples:

Examples

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

We have our array, nums , which contained only 1 valid solution, as expected, and it happened to be (2, 7) at indices (0, 1), respectively.

Example 2:

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

Output: [1,2]
Explanation: Because nums[1] + nums[2] == 6, we return [1, 2].

Strategy & Concepts

Now that we’ve gone through 2 examples, let’s determine our strategy:

• Given a number in the array, we can determine the required complement number that sums to target . This is an important bit of information that will be required in the solution. For example:

Say target = 8.
And, the current number we're looking at is 5.
Then, we can solve for the complement of 5 by:
    complement = target - 5
               = 8 - 5 = 3

• In the very worst case, as shown in Example 2, the two numbers we need are located at the end of nums . So, we’re going to have to potentially iterate over all the elements.
• Knowing the complement is great, but we also need to know it’s respective index in the array. We can utilize a hash map to store numbers as keys, and their indices as values.

I’m going to run through a modified Example 1, and expand on the hash map example mentioned above:

Explanation:

As we iterate over the array (ptr),
  1. Calculate the complement to the current number we're looking at
  2. If the complement is in the table
    2a. Return the value of the complement in the table (the index) and the index of the current number we're looking at
  3. Otherwise, add this current number to the table because the complement to this number hasn't been observed

Coded Solution