Find two numbers summing to target
Company: Aeonea
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an unsorted integer array and a target value, return the indices of two distinct elements whose sum equals the target. Aim for an O(n) time solution and explain your space–time tradeoffs. Discuss how to handle duplicate values, negative numbers, and the case where no valid pair exists. Provide a brief verbal walkthrough and outline the code you would write.
Quick Answer: This question evaluates algorithm design and complexity analysis skills, specifically the ability to identify element pairs in arrays and reason about time-space tradeoffs.
Given an unsorted integer array nums and an integer target, return indices [i, j] (0-based) of two distinct elements such that nums[i] + nums[j] == target. If no such pair exists, return []. If multiple valid pairs exist, return any one. Indices must satisfy i < j. Duplicates and negative values may appear.
Constraints
- 0 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Return indices i < j of two distinct elements
- If no valid pair exists, return []
- Expected solution: O(n) time, O(n) extra space
Hints
- Use a hash map from value to its earliest index seen so far.
- For each index i and value x, check if target - x is already in the map; if so, return [map[target - x], i].
- Store an index for a value only once to keep the earliest occurrence; this handles duplicates correctly.
- If you finish scanning without a match, return []. Negative numbers work the same way.