Two Sum Efficiently | Dataford Interview Questions

DICK'S Sporting Goods systems may need to identify two product prices whose combined value matches a target promotion amount. Given an array of integers nums and an integer target, return the indices of two distinct elements whose values add up to target.

Formal Specification

Implement two_sum(nums, target), where nums is a list of integers and target is an integer. Return a list containing the two zero-based indices in ascending order of discovery. Do not use the same array element twice. Each valid input contains exactly one solution.

Your solution should improve on the brute-force O(n²) approach by using a data structure that supports efficient lookup of previously seen values.

Constraints

2 <= len(nums) <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Exactly one valid pair exists
The same index cannot be used twice

Function Signature

def two_sum(nums, target):

Your question is Two Sum Efficiently. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem