Katkat
Back

Two Sum — Indices Summing to a Target

J.P. MorganSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to trade space for time by using a hash map to achieve linear time complexity when finding a pair of elements that satisfy a target sum.

Problem: Target Index Pair

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to the target.

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Function Signature

def two_sum(nums: List[int], target: int) -> List[int]:

Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Exactly one valid answer exists.

Examples

Example 1: Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2: Input: nums = [3, 2, 4], target = 6 Output: [1, 2]

Edge Cases

  • Array with only two elements.
  • Negative numbers included in the array.
  • The target value is formed by the same number appearing at different indices (e.g., [3, 3] with target 6).

Hints

Hint 1

A brute-force approach would involve nested loops checking every possible pair, but this results in O(n^2) time complexity.

Hint 2

Consider using a hash map (dictionary) to store the values you have already traversed and their corresponding indices.

Hint 3

For each element `x`, check if `target - x` exists in your hash map; if it does, you have found your pair.

Follow-up questions

  • What if the input array is already sorted? Can you solve this in O(1) space complexity?
  • How would you modify your solution to return all unique pairs that sum to the target, rather than just the first valid pair found?
  • If you were given a very large stream of numbers where you cannot fit the entire array in memory, how would you approach finding the target sum?