How do you solve Two Sum on LeetCode?

Two Sum (LeetCode #1) can be solved using Brute Force or Optimal Solution (Hash Map). The optimal approach is Optimal Solution (Hash Map) with O(n) time complexity and O(n) space complexity. Key insight: Using a hash map allows for constant time lookups, which significantly reduces the time complexity from O(n²) to O(n).

What is the brute force solution for Two Sum?

The brute force approach for Two Sum is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible pair of numbers in the array to see if they add up to the target. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution (Hash Map) approach improves this to O(n).

What algorithm or data structure is used to solve Two Sum?

Two Sum uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Two Sum?

When you first see this problem, clarify that you can assume there is exactly one solution and that you cannot use the same element twice. Communicate your thought process clearly; explain how you would check pairs and then transition to using a hash map for efficiency. Mention edge cases such as negative numbers or large values for target, and ensure you discuss the constraints provided.

What are common mistakes when solving Two Sum?

Students often forget to check if the complement exists in the hash map before adding the current number, which can lead to incorrect results. Some may try to use the same index for both numbers, which is not allowed as per the problem statement.

Two Sum

Easy

ArrayHash TableHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (Hash Map)★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a hash map allows us to store the numbers we have seen so far and their indices. This way, we can check in constant time if the complement (target - current number) exists in the map.

⚙️

Algorithm

5 steps

1Step 1: Create an empty hash map to store numbers and their indices.
2Step 2: Loop through each number in the array with its index.
3Step 3: For each number, calculate its complement (target - number).
4Step 4: Check if the complement exists in the hash map. If it does, return the indices of the current number and the complement.
5Step 5: If not, add the current number and its index to the hash map.

solution.py12 lines

1# Full working Python code with comments
2
3def two_sum_optimal(nums, target):
4    num_map = {}
5    for i, num in enumerate(nums):
6        complement = target - num
7        if complement in num_map:
8            return [num_map[complement], i]
9        num_map[num] = i
10
11# Example usage
12print(two_sum_optimal([2, 7, 11, 15], 9))  # Output: [0, 1]

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once, and the hash map operations (insert and lookup) are O(1) on average. The space complexity is O(n) due to the storage of elements in the hash map.

1Using a hash map allows for constant time lookups, which significantly reduces the time complexity from O(n²) to O(n).
2Recognizing that we only need to find one pair of indices can simplify the problem-solving approach.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.