Jobs

Interviews

Discussions

Two Sum

Easy

Uber

4 views

Topics:

ArraysBit Manipulation

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 <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

Two Sum

Easy

Uber

4 views

Topics:

ArraysBit Manipulation

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 <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array?
Can the `nums` array contain duplicate numbers, and if so, does that affect which indices I should return?
Is it guaranteed that the `nums` array will always have at least two elements?
If there are multiple pairs that sum to the target, is there a specific pair I should return (e.g., the pair with the smallest indices)?
Could the target value be outside the possible sums that could be generated from `nums`?

Brute Force Solution

Approach

The brute force approach to this problem is all about trying every single combination. We check each number in the set against every other number to see if they add up to our target value. It's like exhaustively checking every possible pair until we find the right one.

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Add it to the second number, and check if the sum equals our target value.
If not, add it to the third number, and check again.
Keep doing this, adding the first number to every other number in the set.
Once you've gone through all the other numbers, move on to the second number in the set.
Now, add the second number to every number that comes *after* it in the set.
Keep repeating this process, moving through each number in the set and adding it to all the numbers that come after it, until you find a pair that adds up to your target.

Code Implementation

def two_sum_brute_force(numbers, target):
    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare with every number after the current one
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Check if the current pair sums to target
            if numbers[first_number_index] + numbers[second_number_index] == target:
                return [first_number_index, second_number_index]

    # No solution found.
    return []

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force algorithm iterates through the input array of size n. For each element, it compares it with every subsequent element to find a pair that sums to the target value. In the worst case, for the first element it performs (n-1) comparisons, for the second (n-2) comparisons, and so on. This results in a total number of operations that approximates to n * (n-1) / 2. Simplifying this expression, we get a time complexity of O(n²).

Space Complexity

O(1) – The brute force approach described involves iterating through the input array, but it does not create any auxiliary data structures like lists, hash maps, or arrays to store intermediate results. It only uses a fixed number of variables for indexing (e.g., to keep track of which two numbers are currently being added), and these variables require a constant amount of space irrespective of the size of the input array (N). Therefore, the auxiliary space complexity of this algorithm is O(1), indicating constant space.

Optimal Solution

Approach

The efficient way to solve this problem involves remembering information as we go. Instead of checking every possible pair of numbers, we use a tool to quickly see if the number we need has already appeared.

Here's how the algorithm would work step-by-step:

Create a special lookup tool that lets you quickly check if a number exists and where to find it.
Start with the first number in the list.
Calculate what other number you need to reach the desired total.
Use your lookup tool to check if you've seen that needed number already.
If you find it, you're done! You have the two numbers.
If you don't find it, put the current number into your lookup tool, so you can find it later if you need it.
Move to the next number in the list and repeat steps 3-6.
Continue this process until you find a pair or run out of numbers.

Code Implementation

def find_two_sum(number_list, target_sum):
    number_index_map = {}

    for index, number in enumerate(number_list):
        needed_number = target_sum - number

        # Check if the needed number exists in the lookup table
        if needed_number in number_index_map:
            return [number_index_map[needed_number], index]

        # Store the current number and its index in the lookup
        number_index_map[number] = index

    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. Inside the loop, it performs a constant-time lookup in a hash table (or dictionary) to check for the complement. Inserting an element into the hash table also takes constant time on average. Therefore, the dominant operation is the single pass through the array, resulting in a time complexity of O(n).

Space Complexity

O(N) – The provided algorithm uses a lookup tool, which can be implemented using a hash map or dictionary. This data structure stores each number encountered in the input list along with its index. In the worst-case scenario, where no two numbers sum up to the target, the hash map will store all N numbers from the input list. Therefore, the auxiliary space required grows linearly with the input size N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty input array	Return an empty list or null, indicating no solution possible.
Input array with only one element	Return an empty list or null, because two distinct numbers are required.
Input array with two identical elements summing to target	The problem statement says all elements should be distinct. The problem does not define this. Throw an exception or return an error code if this is the case.
Large input array size potentially causing memory issues with a hash map approach	Ensure the hash map implementation can handle the expected number of elements without exceeding memory limits; consider space-optimized data structures if necessary.
Input array containing negative numbers	The hash map approach handles negative numbers correctly.
Integer overflow if two large numbers sum to the target (language specific)	Use a data type that can accommodate the sum, or check for overflow before performing the addition.
The target value is outside the possible sum range given the numbers in the array	The algorithm will not find a match and return an empty array or null, as expected
Array contains duplicate values that could lead to incorrect index return if not handled carefully	Hashmap values will be overwritten which prevents us from accessing the same index twice.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array?
Can the `nums` array contain duplicate numbers, and if so, does that affect which indices I should return?
Is it guaranteed that the `nums` array will always have at least two elements?
If there are multiple pairs that sum to the target, is there a specific pair I should return (e.g., the pair with the smallest indices)?
Could the target value be outside the possible sums that could be generated from `nums`?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Add it to the second number, and check if the sum equals our target value.
If not, add it to the third number, and check again.
Keep doing this, adding the first number to every other number in the set.
Once you've gone through all the other numbers, move on to the second number in the set.
Now, add the second number to every number that comes *after* it in the set.
Keep repeating this process, moving through each number in the set and adding it to all the numbers that come after it, until you find a pair that adds up to your target.

Code Implementation

def two_sum_brute_force(numbers, target):
    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare with every number after the current one
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Check if the current pair sums to target
            if numbers[first_number_index] + numbers[second_number_index] == target:
                return [first_number_index, second_number_index]

    # No solution found.
    return []

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Create a special lookup tool that lets you quickly check if a number exists and where to find it.
Start with the first number in the list.
Calculate what other number you need to reach the desired total.
Use your lookup tool to check if you've seen that needed number already.
If you find it, you're done! You have the two numbers.
If you don't find it, put the current number into your lookup tool, so you can find it later if you need it.
Move to the next number in the list and repeat steps 3-6.
Continue this process until you find a pair or run out of numbers.

Code Implementation

def find_two_sum(number_list, target_sum):
    number_index_map = {}

    for index, number in enumerate(number_list):
        needed_number = target_sum - number

        # Check if the needed number exists in the lookup table
        if needed_number in number_index_map:
            return [number_index_map[needed_number], index]

        # Store the current number and its index in the lookup
        number_index_map[number] = index

    return None

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return an empty list or null, indicating no solution possible.
Input array with only one element	Return an empty list or null, because two distinct numbers are required.
Input array with two identical elements summing to target	The problem statement says all elements should be distinct. The problem does not define this. Throw an exception or return an error code if this is the case.
Large input array size potentially causing memory issues with a hash map approach	Ensure the hash map implementation can handle the expected number of elements without exceeding memory limits; consider space-optimized data structures if necessary.
Input array containing negative numbers	The hash map approach handles negative numbers correctly.
Integer overflow if two large numbers sum to the target (language specific)	Use a data type that can accommodate the sum, or check for overflow before performing the addition.
The target value is outside the possible sum range given the numbers in the array	The algorithm will not find a match and return an empty array or null, as expected
Array contains duplicate values that could lead to incorrect index return if not handled carefully	Hashmap values will be overwritten which prevents us from accessing the same index twice.