Katkat
Back

Return Every Index Pair Whose Values Sum to a Target

J.P. MorganMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle frequency counts and index tracking using hash maps to identify all possible index pairs that sum to a specific target, particularly in the presence of duplicate values.

Problem Statement

Given an array of integers nums and an integer target, write a function that returns a list of all distinct pairs of indices (i, j) such that nums[i] + nums[j] == target and i < j.

Since the array may contain duplicate values, you must account for every possible combination of indices. For example, if the input is [1, 1, 1] and the target is 2, the valid index pairs are (0, 1), (0, 2), and (1, 2).

Function Signature

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

Constraints

  • 1 <= nums.length <= 10^4
  • -10^6 <= nums[i] <= 10^6
  • -2 * 10^6 <= target <= 2 * 10^6

Examples

Example 1: Input: nums = [2, 7, 11, 15], target = 9 Output: [(0, 1)] Explanation: Only the elements at index 0 and 1 sum to 9.

Example 2: Input: nums = [1, 2, 1, 2], target = 3 Output: [(0, 1), (0, 3), (1, 2), (2, 3)] Explanation: Multiple index combinations exist that sum to 3.

Edge Cases

  • Arrays with fewer than 2 elements.
  • Arrays where no pair sums to the target.
  • Arrays containing all identical elements (e.g., [5, 5, 5], target 10).

Hints

Hint 1

Consider using a hash map where keys are the values in the array and values are lists of indices where that number appears.

Hint 2

Iterate through the array once and for each element `nums[i]`, calculate the `complement = target - nums[i]`.

Hint 3

If the complement exists in your hash map, every index previously stored for that complement forms a valid pair with the current index `i`.

Follow-up questions

  • What is the time complexity of your solution in the worst case where all elements are identical?
  • If the input array were sorted, how would that change your approach to finding these pairs?
  • How would you modify your solution if the requirement was to return the number of pairs rather than the pairs themselves, and we needed to optimize for space?