PythonMediumHashing20 min
Find a pair of indices with a target sum
Scan the right index from left to right and return the first possible pair. For that right index choose the smallest matching left index; print -1 if no pair exists. Interviewers use this problem to assess store the first index of each previously seen value.
Input
First line: n and target. Second line: n integers.
Output
Print the result values separated by single spaces; print an empty line for an empty result.
Constraints
0 <= n <= 100000; values and target are between -10^9 and 10^9.
Example
Input
4 9 2 7 11 15
Output
0 1
Example 2 input
5 5 1 1 4 2 3
Output
0 2
Earliest stored indices settle duplicate-value ties.
Public test cases (2)
Input
4 9 2 7 11 15
Expected output
0 1
Input
4 6 3 3 3 3
Expected output
0 1
Hints (2)
- Identify the state needed to avoid repeated work.
- Store the first index of each previously seen value.
Target complexity: time O(n) expected · space O(n)