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.
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.
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!