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
Solution
from typing import List
def two_sum(nums: List[int], target: int) -> List[int]:
"""
Return indices [i, j] with i < j such that nums[i] + nums[j] == target.
Return [] if no such pair exists.
"""
seen = {} # value -> earliest index
for i, x in enumerate(nums):
comp = target - x
if comp in seen:
return [seen[comp], i]
if x not in seen: # keep earliest index only
seen[x] = i
return []
Explanation
Scan the array once while maintaining a hash map from value to its earliest index. For each element x at position i, compute comp = target - x. If comp has been seen before at index j, then nums[j] + nums[i] equals target and we return [j, i]. If not, record x's index if it is the first time we see x. This handles duplicates and negative numbers naturally and ensures distinct indices. If no pair is found, return an empty list.
Time complexity: O(n). Space complexity: O(n).
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.