Two Sum - Video Solutions

Problem Overview: Given an integer array nums and a target value, return the indices of two numbers whose sum equals the target. Each input has exactly one valid pair, and you cannot reuse the same element twice. The challenge is finding that pair efficiently without checking every possible combination.

Approach 1: Brute Force (O(n^2) time, O(1) space)

The most direct solution checks every possible pair of numbers. Use two nested loops: the outer loop picks the first number and the inner loop scans the rest of the array for a second number that satisfies nums[i] + nums[j] == target. Once the pair is found, return their indices. This approach works for any array and requires no extra data structures, so the space complexity stays O(1). The downside is the time complexity: with n elements, you potentially evaluate n(n-1)/2 pairs, resulting in O(n^2) time. It’s useful as a baseline during interviews because it demonstrates clear reasoning before optimizing.

Approach 2: Hash Map (O(n) time, O(n) space)

The optimal solution uses a hash table to track numbers you have already seen while scanning the array once. For each element nums[i], compute its complement target - nums[i]. Check if that complement already exists in the hash map. If it does, you found the required pair and can immediately return the stored index and the current index. If it does not, store the current number and its index in the map and continue iterating.

The key insight is that instead of searching the array repeatedly, the hash map allows constant-time lookups. Each iteration performs a hash lookup and possibly an insertion, both averaging O(1). Because the array is scanned once, the total time complexity becomes O(n). The tradeoff is extra memory: the map may store up to n elements, leading to O(n) space complexity.

This technique is a classic pattern when solving array problems involving complements, frequencies, or fast membership checks. Variants of this idea appear in many interview questions such as Two Sum II, Subarray Sum Equals K, and other problems involving prefix sums and lookups.

Recommended for interviews: Interviewers usually expect the hash map solution because it reduces the runtime from O(n^2) to O(n). Start by explaining the brute force approach to show you understand the problem space, then optimize using a hash map. Demonstrating that transition—from pair comparison to constant-time lookups—shows strong algorithmic thinking.