Return Every Index Pair Whose Values Sum to a Target

Question

Given an array of integers and a target sum, return all unique index pairs whose values add up to the target.

Codemia · Accepted Answer

To solve the problem of finding all unique index pairs in an array that sum to a target, we need to consider both the values and their positions in the array. The goal is to ensure that we return pairs of indices without duplicates and in a way that respects the original order of the array.

A good approach to solve this problem is to use a hash map to keep track of the indices of the numbers we have seen so far. As we iterate through the array, we can check if the complement (target - current number) exists in the hash map. If it does, we can form a valid index pair. This method allows us to achieve a time complexity of O(n).

Here is a Python implementation of the described approach:

```python
def two_sum_indices(nums, target):
    index_map = {}
    result = []

for i, num in enumerate(nums):
        complement = target - num
        if complement in index_map:
            for index in index_map[complement]:
                result.append((index, i))
        if num in index_map:
            index_map[num].append(i)
        else:
            index_map[num] = [i]

return result
```
This function iterates through the list, checking for complements and storing indices in a hash map.

The time complexity of this algorithm is O(n) because we traverse the list once. The space complexity is also O(n) due to the hash map storing indices. This is efficient compared to a naive O(n^2) solution that checks all pairs.

Interviewers will be looking for clarity in your explanation of the problem, the efficiency of your solution, and your ability to handle edge cases, such as when there are no valid pairs or when the input array contains duplicates. They may also probe your understanding of the trade-offs associated with different approaches.

Return Every Index Pair Whose Values Sum to a Target

J.P. Morgan

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

J.P. Morgan Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string