Find Indices of the pair of elements in the Array such that they add up to the Target value

Question

I want to find a target sum in an array by adding integers until it's reached, then return the indexes which add up to the target by using streams.

For example, if the provided array is {1, 2, 3, 4} and the target is 4, the method should print out an array of int consisting of indexes {0,2}, but does not.

The code is as below:

public static int[] twoSum(int[] numbers, int target) {
    IntStream.of(0, numbers.length - 1).boxed()
            .flatMap(i -> IntStream.range(i , numbers.length - 1).boxed()
            .filter(j -> numbers[j] + numbers[i] == target)
            .flatMap(j -> Stream.of(new int[]{i , j}, new int[] {j,i})))
            .forEach(num -> System.out.println(Arrays.toString(num)));

    return numbers;
}

public static void main(String[] args) {
    System.out.println(Arrays.toString(twoSum(new int[]{1,2,5,1}, 4)));
}

Answer 1

Not sure, but if you are using this code exactly, May it is because of the typo you have after foreach. You are initiating the input as nu, but printing it as num.

.forEach(num -> System.out.println(Arrays.toString(num)));

Perhaps replacing this with what you have will solve the problem.

EDIT

Regarding more clarification over comments, It was realized that was an issue with given values and had nothing to do with Java stream API.

Answer 2

Firstly, let's describe the possible ways to address the problem:

• Brute-force approach: iterate over the source array with a nested loop or using a nested stream (reminder: stream is only a mean of iteration) and check for every element whether there's a counterpart for in the array, so that together they constitute the given sum. Time complexity is O(n^2).
• So-called two-pointer approach: sort the given array, define two variables that initially point to the first and the last indices, and then move the pointers. This algorithm could implemented using imperative style only. Time complexity is O(n log n) (because sorting required), which is much better nested loop/streams.
• Create a Map that will store all pair of elements that result into the target sum. The algorithm runs in a linear time O(n). Only two iterations over the source array are required.

The solution below provides a stream-based implementation of the approach that utilizes a Map.

As the first step, we need to generate a map that will associate a value that required to be added to a particular element in order to obtain a target sum (a key) and the index of an array element (a value).

Then create a stream over the indices of the given array, filter out the first element that matches a key in the map and construct a two-value array based on it.

If a result was not found - return an empty array.

public static int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> sumMap = getSumMap(numbers, target);
    
    return IntStream.range(0, numbers.length)
        .filter(i -> sumMap.containsKey(numbers[i]))
        .mapToObj(i -> new int[]{i, sumMap.get(numbers[i])})
        .findFirst()
        .orElse(new int[0]);
}

public static Map<Integer, Integer> getSumMap(int[] numbers, int target) {
    rreturn IntStream.range(0, numbers.length)
        .boxed()
        .collect(Collectors.toMap(
            i -> target - numbers[i], //  a key - dif between target sum and a current element
            Function.identity(),      //  a value - index of the current element
            (left, right) -> left));  //  resolving duplicates
}

main() - demo

public static void main(String[] args) {
    System.out.println(Arrays.toString(twoSum(new int[]{1, 4, 3, 0, 4, 1}, 4)));
}

Output

[0, 2] // indices of the first pair of elements (1, 3) that can produce the sum of `4`

Answer 3

Instead of using a for loop you can nest two IntStreams to produce the desired result (as I understand it). This will return all pairs that sum to the target value. This does not include elements of the array that added to themselves equal the target. So for a target of 4, [2, 2] is not included as a result

int[] arr1 = { 1, 2, 3, 4, 5, -2, -1, -3, -4, -5 };

int[][] array = twoSum(arr1, 4);

for (int[] a : array) {
    System.out.println(Arrays.toString(a));
}

prints

[1, 3]
[5, -1]

• First, stream a range of ints from 0 to one less than the array size.
• then use boxed to convert the int to an object.
• Then you flatMap (combine the nested streams into one) another IntStream starting with one more than the previous stream, but the full length of the array.
• still within the flatMap construct, and using the values of the IntStreams as the indices to the supplied array, filter away values that don't sum to the target, and create an array of the two numbers that did add up (this could also be replaced with the indices of the array if desired).
• Then return this array of arrays as a result.

public static int[][] twoSum(int[] numbers, int target) {
    return IntStream.range(0, numbers.length - 1)
            .boxed()
            .flatMap(i -> IntStream.range(i + 1, numbers.length)
                    .filter(k -> numbers[i] + numbers[k] == target)
                    .mapToObj(k -> new int[] { numbers[i],numbers[k] }))
            .toArray(int[][]::new);
}