Two Sum [Amazon Python Interview Question]

Given an list of integers called , and an integer , return the index of the two numbers which sum up to the target. Do not use the same list element twice.

Clarifications:

• Assume there aren't multiple valid solutions.
• In case there is no valid solution, return [-1, -1].
• Return the indexes in increasing order (i.e. [1,3], NOT [3,1]).

Example #1

Input: input = [1, 4, 6, 10], target = 10

Output: [1, 2]

Explanation: Because 4 + 6 == 10, we return the index of elements 4 and 6, which is [1, 2]

Example #2

Input: input = [1, 4, 6, 10], target = 11

Output: [0, 3]

Explanation: Because input[0] + input[3] == 11, we return [0, 3].

Example #3

**Input: **input = [1, 4, 6, 10], target = 2

Output: [-1, -1]

Explanation: There are no two elements we can pick that sum up to 2. Remember, you can't use the same element twice!

Brute-Force Two Sum Solution

The brute-force approach is to loop through each element () in the input list, and have a second inner for-loop .

Inside that inner for-loop, we'll check if the input's $i^{th} + j^{th}$ element is equal to the $target$.

If we don't find a valid pair, we return [-1, -1],

Brute-Force Performance

The time complexity of this code is $O(n^2)$ because we use a double for-loop. The space complexity of this code is $O(1)$ because the space required isn't a function of the input list size.

Single Pass With Dictionary Solution

To improve our runtime complexity, we can iterate over the list, and then use a dictionary to quickly see if an element's complement was already seen. By complement, we mean the target - current element.

If the dictionary says we've seen the complement already, we return the index of the current element and the complement's index.

This code is more efficient, because in Python, dictionaries are implemented as hash tables, which provide efficient key-value lookups. The run-time performance of dictionary retrieval has an average-case time complexity of O(1), which means that the time it takes to retrieve a value from a dictionary is roughly constant and does not depend on the number of items (key-value pairs) in the dictionary.

Single Pass With Dictionary Performance

Traversing each element in the list once means the time complexity is $O(n). Remember: our dictionary lookups are$O(1)$ so won't affect the run-time complexity.

Because we are creating a dictionary to store the $n$ elements, the space complexity is $O(n)$.

Not that this dictionary-based solution, when compared to the brute-force solution, traded off space for speed! In a coding interview, being able to note trade-offs in terms of space & time complexity helps you be perceived as a stronger coder!