2 Sum Problem | 2 types of the same problem for Interviews | Brute-Better-Optimal

Summary

The video explains two variations of the Two Sum problem and develops solutions ranging from brute force to more efficient approaches.

Problem variations

Given an integer array and a target:

1. Existence: Determine whether any two distinct elements add up to the target.
2. Indices: Return the positions of two elements whose values add up to the target.

For example, with a target of 14, the values 6 and 8 form a valid pair. The first variation returns “yes”; the second returns their indices.

Approaches

Brute force

Try each element with every other element. If their sum equals the target, return “yes” or the pair of indices.

To avoid pairing an element with itself or repeating pairs, start the inner loop at i + 1.

• Time: O(n²)

Hash map

Traverse the array once, keeping previously seen values in a map. For each current value x, calculate its complement: target - x.

If the complement is already in the map, the pair has been found. Return “yes” or the current index and the saved index. Otherwise, store the current value and its index, then continue.

This approach supports both problem variations and is preferred for returning indices.

• Time: O(n) on average with a hash map. Worst-case behavior depends on the map implementation; an ordered map typically gives O(n log n).
• Space: O(n)

Sort and use two pointers

Sort the array, then place one pointer at the beginning and another at the end.

• If the two values sum to the target, the pair is found.
• If the sum is too small, move the left pointer right to increase it.
• If the sum is too large, move the right pointer left to decrease it.
• If the pointers meet or cross without finding the target, no pair exists.

This is useful for the existence variation when avoiding a hash map.

• Time: O(n log n) overall due to sorting; the pointer scan is O(n).
• Space: The scan uses O(1) extra space, though sorting may mutate the array or require implementation-dependent space.

To return indices with the two-pointer method, keep the original indices alongside the values while sorting. This adds storage and makes the method less suitable than hashing for the index-returning variation.

Speakers and sources

• Speaker: A single presenter associated with the Take U Forward channel and referred to in the subtitles as Striver.
• Sources mentioned: The presenter refers to a Two Sum problem link and a time-complexity lesson. No additional speakers are featured.