Couple Sum

Given an array of integers, find two numbers such that they sum up to a specific target.
The method coupleSum should return the indices of the two numbers in the array, where index1 must be less than index2.
Please note that the indices are not zero based, and you can assume that each input has exactly one solution. Target linear runtime and space complexity.

Example:

Input Array : {2, 3, 4, 7}  
Target      : 7
Output      : {2, 3}

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

Many a time, the required runtime or space complexity can shed light on the kind of data structure required to solve a problem. In this case, since we are targeting a linear runtime and are allowed to use linear space, a HashMap is a sound choice.

A more detailed explanation

Think about the key and value that you will store in the HashMap. Let's consider the example shown above. Iterating across the array [2, 3, 4, 7], at each step let us store the key as target - arr[i], and the value i+1 (since the output is not zero-indexed). Now, if we are at i=1, or arr[i] = 3 and store key = 7 - 3=4 and value = 1 + 1 = 2, then when we get to the next index i = 2, we just need to check if they key arr[i] = 4 exists in the HashMap.

TLDR: Store the difference between the target and the current index in the HashMap so that you can compare subsequent numbers in a single pass!

public static int[] coupleSum(int[] numbers, int target) {
    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Couple Sum

Quick hint to get things rolling

A more detailed explanation

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :