Two Sum - Return Indices

Given an array of n integers and an integer target, find two distinct indices i and j (0-indexed, i < j) such that arr[i] + arr[j] equals target. Scanning the array from left to right and looking up each element's complement in a hash map of previously seen values, report the pair found at the smallest possible j; if more than one i qualifies for that j, use the earliest (first-seen) one. If no such pair exists, print -1 -1.

Input: The first line contains a single integer n, the size of the array. The second line contains n space-separated integers. The third line contains the integer target. Output: Two space-separated integers i and j (the 0-indexed pair), or -1 -1 if no valid pair exists.

2 <= n <= 10^5. -10^9 <= arr[i] <= 10^9. -10^9 <= target <= 10^9.

Storing only the EARLIEST index for each distinct value (never overwriting it on a later duplicate) is exactly what guarantees the reported pair has the smallest possible j, with ties broken by the earliest i - precisely matching this problem's specific tie-breaking requirement.

Find two positions in an array whose values add up to a target sum, and report their indices. Brute force: Check every possible pair of indices directly with two nested loops - this costs O(n²), unnecessary when a hash map can find each element's complement in O(1). Optimised: A hash map lets you check 'has the complement I need already appeared' in O(1) at every step, turning an all-pairs search into a single linear pass - checking BEFORE inserting the current value also naturally avoids ever pairing an element with itself.

1. Scan the array left to right, keeping a hash map of every value seen so far, mapped to the EARLIEST index it occurred at. 2. For each new element at index j, check whether (target - current value) already exists in the map BEFORE inserting the current element. 3. If it exists, you've found your pair immediately; only insert a value into the map the FIRST time it's seen, so the map always holds the earliest possible index.

Time: O(n) - one single pass, with O(1) average-case hash map lookups. Space: O(n), for the hash map of values seen so far.

If no pair sums to target, print -1 -1. If the array contains duplicate values, a pair may use two equal elements at different indices.

This is likely the single most famous hash-map interview question in existence - be ready to state the O(n²)-to-O(n) improvement instantly and explain precisely why checking the complement BEFORE inserting the current value matters.