Jobs

Interviews

Discussions

Two Sum

Easy

Asked by:

+52

More companies

2.9K views

Topics:

Arrays

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?

Try coding it in LeetCode

Two Sum

Easy

Asked by:

+46

More companies

2.9K views

Topics:

Arrays

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?

Try coding it in LeetCode

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:

Can the input array `nums` contain duplicate numbers, and if so, how should I handle cases where multiple pairs sum to the target?
Is it guaranteed that there will always be exactly one pair of distinct elements that sum up to the target, or should I consider scenarios where no such pair exists?
Are the numbers in the `nums` array guaranteed to be integers, or could they be floating-point numbers?
What is the expected behavior if `nums` is empty or contains only a single element?
If multiple distinct pairs sum to the target, which pair of indices should I return? For example, should I return the first one found, or the one with the smallest indices?

Brute Force Solution

Approach

The brute force method for Two Sum involves checking every single possible pair of numbers in the given collection to see if they add up to the target number. It's like trying every combination until you find the right one.

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

Pick the first number from the collection.
Now, go through every other number in the collection, one by one.
For each of those other numbers, add it to the first number you picked.
Check if this sum is exactly equal to the target number you're looking for.
If it is, you've found your pair, and you can stop.
If it's not, put that first number back and pick the next number from the collection.
Repeat the process of adding it to all the other numbers and checking the sum.
Continue doing this, systematically trying every unique pair of numbers, until you discover the pair that perfectly matches the target sum.

Code Implementation

def two_sum_brute_force(numbers, target_sum):    number_count = len(numbers)    # We need to iterate through each number in the list to consider it as the first element of a potential pair.    for first_element_index in range(number_count):        # For each chosen first element, we must check it against all subsequent elements to form unique pairs.        for second_element_index in range(first_element_index + 1, number_count):            # This check is crucial to see if the current pair sums up to the desired target.            if numbers[first_element_index] + numbers[second_element_index] == target_sum:                return [first_element_index, second_element_index]    # If no pair is found after checking all combinations, it signifies that no solution exists.    return []

Big(O) Analysis

Time Complexity

O(n^2) – The brute force approach involves iterating through each number in the collection (let's call the size of the collection n). For each of these n numbers, we then iterate through all the remaining numbers in the collection to form pairs and check their sum against the target. This means that for the first number, we perform approximately n-1 checks, for the second, n-2 checks, and so on. The total number of pair checks is roughly the sum of an arithmetic series, which is approximately n * (n-1) / 2. As n grows, the dominant term is n^2, leading to a time complexity of O(n^2).

Space Complexity

O(1) – The brute force approach described involves iterating through pairs of numbers within the input collection. It only uses a few variables to store the current numbers being considered and their sum. The amount of extra memory used does not depend on the size of the input collection (N), and therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

Instead of checking every single number against every other number, we can use a clever trick to quickly find if the 'missing' number needed to reach our target exists. This involves remembering the numbers we've already seen so we can instantly look them up later.

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

Imagine you have a list of numbers and you want to find two that add up to a specific target value.
Go through the list one number at a time.
For each number, figure out what other number you would need to find to reach the target (let's call this the 'complement').
Before you move on, quickly jot down the number you just looked at and where you found it, so you don't forget it.
Now, check if you've already 'jotted down' the complement you just calculated.
If you have, then you've found your pair! You know the current number and the number you jotted down earlier that matches the complement.
If you haven't found the complement yet, continue to the next number in the list and repeat the process.
By instantly checking if the required complement has been seen, you avoid having to compare every number with every other number.

Code Implementation

def find_two_sum_indices(numbers_list, target_value):
    seen_numbers_map = {}

    for current_index, current_number in enumerate(numbers_list):
        complement_needed = target_value - current_number

        # We need to check if the complement has been seen before to form a pair.
        if complement_needed in seen_numbers_map:
            return [seen_numbers_map[complement_needed], current_index]

        # Store the current number and its index for future lookups.
        seen_numbers_map[current_number] = current_index

    # If no pair is found after checking all numbers.
    return []

Big(O) Analysis

Time Complexity

O(n) – We iterate through the input list of size n exactly once. For each element, we perform a constant time lookup in a hash map (or dictionary) to check for the complement. Since we only traverse the list once and each operation within the loop takes constant time, the total time complexity is directly proportional to the number of elements, n. This results in a runtime of O(n).

Space Complexity

O(n) – The solution uses a hash map (or similar dictionary-like structure) to store numbers encountered so far along with their indices. In the worst-case scenario, where no pair sums to the target until the very last element is processed, all N elements of the input list might be stored in this hash map. Therefore, the auxiliary space complexity is directly proportional to the number of elements in the input list, denoted as N. This leads to a space complexity of O(n).

Edge Cases

Case	How to Handle
Empty or null input array	An empty or null input array should result in an empty list being returned as no pair can be found.
Array with fewer than two elements	If the array has less than two elements, it's impossible to find two distinct numbers, so an empty list should be returned.
No pair sums to the target	The algorithm should iterate through the entire array and if no pair is found, it should return an empty list.
Multiple pairs sum to the target	The problem statement implies returning any valid pair, so the first one found is acceptable.
Array contains duplicate numbers	The hash map approach correctly handles duplicates by storing and checking against previous elements; we must ensure we don't use the same element twice by checking if the complement exists and is not the current element's index.
Target is exactly twice one of the numbers	The solution must ensure it doesn't return the index of the same element twice; checking if the complement's index is different from the current index is crucial.
Array contains negative numbers and zero	Negative numbers and zeros are handled correctly by the arithmetic operations and the hash map lookup.
Large input array (scalability)	A hash map approach provides O(n) time complexity which scales efficiently for large arrays.

Empty or null input array

How to Handle:

An empty or null input array should result in an empty list being returned as no pair can be found.

Array with fewer than two elements

How to Handle:

If the array has less than two elements, it's impossible to find two distinct numbers, so an empty list should be returned.

No pair sums to the target

How to Handle:

The algorithm should iterate through the entire array and if no pair is found, it should return an empty list.

Multiple pairs sum to the target

How to Handle:

The problem statement implies returning any valid pair, so the first one found is acceptable.

Array contains duplicate numbers

How to Handle:

The hash map approach correctly handles duplicates by storing and checking against previous elements; we must ensure we don't use the same element twice by checking if the complement exists and is not the current element's index.

Target is exactly twice one of the numbers

How to Handle:

The solution must ensure it doesn't return the index of the same element twice; checking if the complement's index is different from the current index is crucial.

Array contains negative numbers and zero

How to Handle:

Negative numbers and zeros are handled correctly by the arithmetic operations and the hash map lookup.

Large input array (scalability)

How to Handle:

A hash map approach provides O(n) time complexity which scales efficiently for large arrays.

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:

Can the input array `nums` contain duplicate numbers, and if so, how should I handle cases where multiple pairs sum to the target?
Is it guaranteed that there will always be exactly one pair of distinct elements that sum up to the target, or should I consider scenarios where no such pair exists?
Are the numbers in the `nums` array guaranteed to be integers, or could they be floating-point numbers?
What is the expected behavior if `nums` is empty or contains only a single element?
If multiple distinct pairs sum to the target, which pair of indices should I return? For example, should I return the first one found, or the one with the smallest indices?

Brute Force Solution

Approach

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

Pick the first number from the collection.
Now, go through every other number in the collection, one by one.
For each of those other numbers, add it to the first number you picked.
Check if this sum is exactly equal to the target number you're looking for.
If it is, you've found your pair, and you can stop.
If it's not, put that first number back and pick the next number from the collection.
Repeat the process of adding it to all the other numbers and checking the sum.
Continue doing this, systematically trying every unique pair of numbers, until you discover the pair that perfectly matches the target sum.

Code Implementation

def two_sum_brute_force(numbers, target_sum):    number_count = len(numbers)    # We need to iterate through each number in the list to consider it as the first element of a potential pair.    for first_element_index in range(number_count):        # For each chosen first element, we must check it against all subsequent elements to form unique pairs.        for second_element_index in range(first_element_index + 1, number_count):            # This check is crucial to see if the current pair sums up to the desired target.            if numbers[first_element_index] + numbers[second_element_index] == target_sum:                return [first_element_index, second_element_index]    # If no pair is found after checking all combinations, it signifies that no solution exists.    return []

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have a list of numbers and you want to find two that add up to a specific target value.
Go through the list one number at a time.
For each number, figure out what other number you would need to find to reach the target (let's call this the 'complement').
Before you move on, quickly jot down the number you just looked at and where you found it, so you don't forget it.
Now, check if you've already 'jotted down' the complement you just calculated.
If you have, then you've found your pair! You know the current number and the number you jotted down earlier that matches the complement.
If you haven't found the complement yet, continue to the next number in the list and repeat the process.
By instantly checking if the required complement has been seen, you avoid having to compare every number with every other number.

Code Implementation

def find_two_sum_indices(numbers_list, target_value):
    seen_numbers_map = {}

    for current_index, current_number in enumerate(numbers_list):
        complement_needed = target_value - current_number

        # We need to check if the complement has been seen before to form a pair.
        if complement_needed in seen_numbers_map:
            return [seen_numbers_map[complement_needed], current_index]

        # Store the current number and its index for future lookups.
        seen_numbers_map[current_number] = current_index

    # If no pair is found after checking all numbers.
    return []

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	An empty or null input array should result in an empty list being returned as no pair can be found.
Array with fewer than two elements	If the array has less than two elements, it's impossible to find two distinct numbers, so an empty list should be returned.
No pair sums to the target	The algorithm should iterate through the entire array and if no pair is found, it should return an empty list.
Multiple pairs sum to the target	The problem statement implies returning any valid pair, so the first one found is acceptable.
Array contains duplicate numbers	The hash map approach correctly handles duplicates by storing and checking against previous elements; we must ensure we don't use the same element twice by checking if the complement exists and is not the current element's index.
Target is exactly twice one of the numbers	The solution must ensure it doesn't return the index of the same element twice; checking if the complement's index is different from the current index is crucial.
Array contains negative numbers and zero	Negative numbers and zeros are handled correctly by the arithmetic operations and the hash map lookup.
Large input array (scalability)	A hash map approach provides O(n) time complexity which scales efficiently for large arrays.

Empty or null input array

How to Handle:

An empty or null input array should result in an empty list being returned as no pair can be found.

Array with fewer than two elements

How to Handle:

If the array has less than two elements, it's impossible to find two distinct numbers, so an empty list should be returned.

No pair sums to the target

How to Handle:

The algorithm should iterate through the entire array and if no pair is found, it should return an empty list.

Multiple pairs sum to the target

How to Handle:

The problem statement implies returning any valid pair, so the first one found is acceptable.

Array contains duplicate numbers

How to Handle:

Target is exactly twice one of the numbers

How to Handle:

The solution must ensure it doesn't return the index of the same element twice; checking if the complement's index is different from the current index is crucial.

Array contains negative numbers and zero

How to Handle:

Negative numbers and zeros are handled correctly by the arithmetic operations and the hash map lookup.

Large input array (scalability)

How to Handle:

A hash map approach provides O(n) time complexity which scales efficiently for large arrays.