Quick Overview

This question evaluates algorithm design and complexity analysis skills, specifically the ability to identify element pairs in arrays and reason about time-space tradeoffs.

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.

Overview: 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

  1. Use a hash map from value to its earliest index seen so far.
  2. For each index i and value x, check if target - x is already in the map; if so, return [map[target - x], i].
  3. Store an index for a value only once to keep the earliest occurrence; this handles duplicates correctly.
  4. If you finish scanning without a match, return []. Negative numbers work the same way.

Loading coding console...

Show the approach

Approach

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)