Practice question from Foundation: Arrays & Strings
A developer writes this code to find two numbers that sum to a target: This works but times out on large inputs. Which optimization reduces O(n²) to O(n)? A. Sort the array first, then use binary search for each element's complement B. Use a hash map to store seen numbers and check for complements in O(1) time C. Use two pointers from opposite ends if the array is sorted D. Implement the inner loop with list comprehension for faster iteration E. Cache results of previous computations using memoization
def two_sum(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]Answer
B
Explanation
The hash map pattern is the optimal solution for the unsorted Two Sum problem. As you iterate through the array once, you store each number and its index in a hash map. For each new number, you check if its complement (target - current) exists in the map in O(1) time. This eliminates the nested loop, reducing complexity from O(nĀ²) to O(n). Option A would be O(n log n) for sorting plus O(n log n) for n binary searches. Option C requires the array to be sorted first. Options D and E don't fundamentally change the algorithmic complexity.