Two Sum Amazon Python Interview Question

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

Clarifications:

• There is at most one solution.
• If there is no valid solution, return [-1, -1].
• Return the indices in increasing order (i.e. [1,3], NOT [3,1]).

Example #1

Input: nums = [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: nums = [1, 4, 6, 10], target = 11

Output: [0, 3]

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

Example #3

Input: nums = [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 , and have a second inner loop for .

Inside that inner for-loop, we'll check if is equal to the .

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 size of .

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 minus the 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 it won't affect the run-time complexity.

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

Note 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!