Finding out the indices of common elements in two array lists having duplicate elements

Question

I have two lists which are also having some duplicate elements , i am converting this list to map as key value pair with element index as the value for the key - element

List 1 : [1, 2, 3, 4, 5, 6, 7, 2] =>

MAP 1 (Map, List>) : {1=[0], 2=[1, 7], 3=[2], 4=[3], 5=[4], 6=[5], 7=[6]}

List 2 : [3, 3, 2, 4, 7]

=> MAP 2 (Map, List>) : {2=[2], 3=[0, 1], 4=[3], 7=[4]}

i am trying to collect matching keys from both of the maps and club it another map

For above two it would give the result : {[2]=[0, 1], [3]=[3], [6]=[4], [1, 7]=[2]}

Post this , i am taking the cartesian product of key , values and only retaining the unique elements

Final output [[0, 2], [1, 2], [3, 3], [4, 6], [2, 1], [2, 7]] . These is the indices of common elements

Below is the code that i have come up with to achieve this , is there any better way i can achieve the same . I feel it will be too much costly at run time for larger lists .

 List<List<Integer>> cartesianProduct = new ArrayList<>();
 List<String> distinct1 = Arrays.asList("1", "2", "3", "4", "5", "6", "7", "2")
 List<String> distinct2 = Arrays.asList["3", "3", "2", "4", "7"] 
 Map<String, List<Integer>> result1 = IntStream.range(0, distinct1.size()).boxed()
 .collect(Collectors.groupingBy(i -> distinct1.get(i)));
 Map<String, List<Integer>> result2 = IntStream.range(0, distinct2.size()).boxed()
 .collect(Collectors.groupingBy(i -> distinct2.get(i)));
 result1.entrySet().stream()
 .filter(x -> result2.containsKey(x.getKey()))
 .collect(Collectors.toMap(x -> x.getValue(), x -> result2.get(x.getKey())))
 .entrySet().forEach(a1 -> a1.getValue().stream()
 .forEach(b1 -> a1.getKey().stream().forEach(c1 -> cartesianProduct.add(Arrays.asList(b1, c1)))));
 List<List<Integer>> listWithoutDuplicates = cartesianProduct.stream()
 .distinct()
 .collect(Collectors.toList());

Answer 1

Firstly, try to make sure that code you post here compiles. Now you have missing semicolons on the lines

List<String> distinct1 = Arrays.asList("1", "2", "3", "4", "5", "6", "7", "2")
List<String> distinct2 = Arrays.asList["3", "3", "2", "4", "7"] 

and also the last of these two lines has [...] instead of (...).

It was also a bit difficult to actually figure out what your code was supposed to do, but I think I understand it now.

It seems you want to create a list of pairs of some sort. So instead of ending with a List<List<Integer>>, you can create a Pair class

public final class Pair<S, T> {
 private final S left;
 private final T right;
 public Pair(S left, T right) {
 this.left = left;
 this.right = right;
 }
 public S left() {
 return left;
 }
 public T right() {
 return right;
 }
 // equals and hashCode
 ...
}

and have a List<Pair<Integer, Integer>> instead.

Then you can create a method which given two Lists creates the cartesian product

public List<Pair<S, T>> cartesianProduct(List<S> firstList, List<T> secondList) {
 return firstList.stream()
 .flatMap(x -> secondList.stream().map(y -> new Pair<>(x, y)))
 .collect(Collectors.toList());
}

During the construction of your cartesian list, you collect your intermediate results into a Map. This step is not needed as you can now immediately convert to a list of pairs. Also, it is usually not a good idea to have a List as keys of a Map as the List is mutable. Map expects the hash code of the keys to not change which is a possibility when using Lists as keys.

Removing the Map step in the process we get

List<Pair<Integer, Integer>> listWithoutDuplicates = result1.entrySet().stream()
 .filter(x -> result2.containsKey(x.getKey()))
 .flatMap(x -> cartesianProducts(result2.get(x.getKey()), x.getValue()).stream())
 .distinct()
 .collect(Collectors.toList());