Two Sum

Question 1

What is the classic problem discussed in the text?

Answer 1

Two Sum

Question 2

List keywords that should stand out when recognizing the Two Sum problem.

Answer 2

• return indices
• two numbers
• add up to target
• exactly one solution
• don’t use the same element twice

Question 3

What type of problem is the Two Sum problem categorized as?

Answer 3

Hashing problem

Question 4

What are the constraints you can assume in the Two Sum problem?

Answer 4

• There is always exactly one solution
• You can return the indices in any order
• Don’t reuse the same index

Question 5

What is the goal of the Two Sum problem?

Answer 5

Find two numbers in the array that sum to the target and return their indices.

Question 6

Describe the brute force approach to solving the Two Sum problem.

Answer 6

For each element, check every other element to see if the sum equals the target.

Question 7

What is the time complexity of the brute force approach?

Answer 7

O(n²)

Question 8

What is the best approach to optimize the Two Sum problem?

Answer 8

Using a hash map

Question 9

What is the core idea of the hash map approach?

Answer 9

Store each number in a hash map with its index and check if the complement exists.

Question 10

What is the time complexity of the optimized hash map approach?

Answer 10

O(n)

Question 11

What is the space complexity of the optimized hash map approach?

Answer 11

O(n)

Question 12

What should you clarify in an interview when discussing the Two Sum problem?

Answer 12

• Can I assume there’s only one solution?
• Can the same number be used twice?

Question 13

What should you do after quickly discussing the brute force method?

Answer 13

Propose the hash map approach.

Question 14

In the hash map approach, when should you add the number to the hash map?

Answer 14

After checking the complement to avoid using the same element twice.

Question 15

Provide an example of how the Two Sum algorithm works with nums = [2, 7, 11, 15] and target = 9.

Answer 15

• Iteration 0: num = 2, complement = 7 → not in seen, store 2:0
• Iteration 1: num = 7, complement = 2 → found! return [0, 1]

Question 16

What is the summary of approaches for the Two Sum problem?

Answer 16

• Brute Force: O(n²), O(1)
• Hash Map: O(n), O(n)

Question 17

What problem is this?
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.

Answer 17

Two Sum