1 — Two Sum

Problem Description

Restating Info We’re Already Given:

• 2 inputs, nums and target
• Array num of all integers
• Only one answer exists and there is always exactly one solution
• You may not use the element twice
• 2 ≤ nums.length ≤ 10⁴
• -10⁹ ≤ nums[i] ≤ 10⁹
• -10⁹ ≤ target ≤ 10⁹

Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):

• What should we do in the case there is no solution? (If that wasn’t part of the problem statement)
• Are we guaranteed a solution exists? (If that wasn’t part of the problem statement)
• Does the order of the 2 indices in the output list matter?
• Can I assume anything about the nums array? (i.e. sorted, duplicates, etc.)

Discuss Naive Solution:

Given that there exists exactly one solution, we can solve this problem in O(n²) time by checking every pair of indices. This would equate to len(nums) choose 2 checks at worst, which is O(n²).

Discuss Optimal Solution:

In order to solve this problem optimally, we have to visit all the indices at least once. Thus, the optimal solution will run in O(n) time. Firstly, we have to store seen numbers and their corresponding indices. To do that, we should use a dictionary. To iterate through the list’s indices and values in Python, we can use enumerate().

For an index, we check if target - curr_num is in the dictionary.

• If it is, then we’re done, since curr_num + (target - curr_num) = target. We take the current index and the index target-curr_num was located at (accessible in our dictionary) and return that.
• If it isn’t, we need to store the value and its corresponding index in the dictionary.

Code Optimal Solution:

https://leetcode.com/submissions/detail/682514031/

Runtime/Space Complexity:

By the time we’re done processing the last element, we are guaranteed to have our answer and the problem is solved in 1 pass. In that worst case, we need to store all but the last element in the dictionary (one of the indices that sum up to target is the last index). Thus, the time complexity is O(n) and the space complexity is O(n) for a list of length n.

Test Cases:

• length 2 list
• array that contains 2 (or more) of same number, target number is that number * 2
• target == -10⁹ and target == 10⁹: check in case integer overflow when calculating values (if coding in non-pure Python)