1. Two Sum

Given an array of integers and a target value, print the 0-indexed positions of the two numbers that add up to the target, space-separated. Assume exactly one valid answer exists, and read input as: first line is the array (space-separated integers), second line is the target.

Input: The first line contains space-separated integers (the array). The second line contains a single integer, the target. Output: Print the two 0-indexed positions of the numbers that add up to the target, space-separated.

2 <= array length <= 10^4 -10^9 <= values <= 10^9

You only need to check for the complement of numbers ALREADY seen, not the whole array - this one-pass property is what makes the hash map approach both correct and fast.

You're given a list of numbers and a target. Find the two numbers that add up exactly to the target, and report their positions. Brute force: Check every possible pair of numbers directly (two nested loops), testing if they sum to the target - this costs O(n²), fine for small arrays but slow once n grows into the thousands. Optimised: A hash map turns 'has this partner been seen' into an instant O(1) lookup, so you only ever need ONE pass through the array instead of comparing every pair - remember each number as you go, and check for its complement before adding it.

Pair each value with its original index, sort the pairs by value, then use two pointers starting at both ends moving inward: if the sum is too small advance the left pointer, if too large retreat the right pointer, and stop when the sum matches the target. Sorting lets the two-pointer scan eliminate half the remaining search space at each step instead of checking every pair, at the cost of needing to remember original indices since the array order is disturbed. Time: O(n log n) Space: O(n)

Walk through the array once, and for each value check whether (target - value) has already been seen, storing each value's index in a hash map as you go. This works because by the time you reach the second element of the answer pair, its complement is guaranteed to already be in the map, letting you find the pair in a single pass without any sorting overhead. Time: O(n) Space: O(n)

Try every pair of positions (i, j) with i < j and check whether the two values at those positions add up to the target. This directly checks all possible pairs, so it is guaranteed to find the unique valid answer, but it wastes time re-checking combinations that a smarter lookup could rule out instantly. Time: O(n^2) Space: O(1)

1. Walk through the array once, keeping a running 'seen so far' lookup of numbers and their positions. 2. For each new number, compute what its partner would need to be (target minus this number). 3. Check if that partner has already been seen - if so, you've found your pair. 4. If not, add the current number to the lookup and keep going.

Time: A single pass through the array with instant lookups each time - O(n), proportional only to the array's size. Space: O(n), for the hash map storing numbers seen so far.

Test the minimum size n = 2 (only one possible pair), n = 10^4 for performance, and arrays containing negative values.

This is often the very FIRST problem in any technical interview - be fast and precise, and be ready to immediately extend the idea to 3Sum/4Sum if asked (as covered in the Hashing category).