# Minimum Index Sum for Common Elements of Two Lists

Ram and Shyam want to choose a website to learn programming and they both have a list of favorite websites represented by strings.
You need to help them find out their common interest with the least index sum. If there is a choice tie between answers, print all of them with no order requirement. Assume there always exists an answer.

Examples:

```Input : ["GeeksforGeeks", "Udemy", "Coursera", "edX"]
Output : "GeeksforGeeks"
Explanation : GeeksforGeeks is the only common website
in two lists

Input : ["Udemy", "GeeksforGeeks", "Coursera", "edX"]
Output : "GeeksforGeeks" "Udemy"
Explanation : There are two common websites and index sum
of both is same.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Naive Method:

The idea is to try all index sums from 0 to sum of sizes. For every sum, check if there are pairs with given sum. Once we find one or more pairs, we print them and return.

## C++

 `#include ` `using` `namespace` `std; ` ` `  `// Function to print common strings with minimum index sum ` `void` `find(vector list1, vector list2) ` `{ ` `    ``vector res; ``// resultant list ` `    ``int` `max_possible_sum = list1.size() + list2.size() - 2; ` ` `  `    ``// iterating over sum in ascending order  ` `    ``for` `(``int` `sum = 0; sum <= max_possible_sum ; sum++)  ` `    ``{ ` `        ``// iterating over one list and check index  ` `        ``// (Corresponding to given sum) in other list ` `        ``for` `(``int` `i = 0; i <= sum; i++)  ` `         `  `            ``// put common strings in resultant list   ` `            ``if` `(i < list1.size() &&  ` `                ``(sum - i) < list2.size() &&  ` `                ``list1[i] == list2[sum - i]) ` `                ``res.push_back(list1[i]);          ` ` `  `        ``// if common string found then break as we are ` `        ``// considering index sums in increasing order. ` `        ``if` `(res.size() > 0)  ` `            ``break``; ` `    ``} ` ` `  `    ``// print the resultant list ` `    ``for` `(``int` `i = 0; i < res.size(); i++)  ` `        ``cout << res[i] << ``" "``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``// Creating list1 ` `    ``vector list1; ` `    ``list1.push_back(``"GeeksforGeeks"``); ` `    ``list1.push_back(``"Udemy"``); ` `    ``list1.push_back(``"Coursera"``); ` `    ``list1.push_back(``"edX"``); ` ` `  `    ``// Creating list2 ` `    ``vector list2; ` `    ``list2.push_back(``"Codecademy"``); ` `    ``list2.push_back(``"Khan Academy"``); ` `    ``list2.push_back(``"GeeksforGeeks"``); ` ` `  `    ``find(list1, list2); ` `    ``return` `0; ` `} `

## Java

 `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `// Function to print common Strings with minimum index sum ` `static` `void` `find(Vector list1, Vector list2) ` `{ ` `    ``Vector res = ``new` `Vector<>(); ``// resultant list ` `    ``int` `max_possible_sum = list1.size() + list2.size() - ``2``; ` ` `  `    ``// iterating over sum in ascending order  ` `    ``for` `(``int` `sum = ``0``; sum <= max_possible_sum ; sum++)  ` `    ``{ ` `        ``// iterating over one list and check index  ` `        ``// (Corresponding to given sum) in other list ` `        ``for` `(``int` `i = ``0``; i <= sum; i++)  ` `         `  `            ``// put common Strings in resultant list  ` `            ``if` `(i < list1.size() &&  ` `                ``(sum - i) < list2.size() &&  ` `                ``list1.get(i) == list2.get(sum - i)) ` `                ``res.add(list1.get(i));        ` ` `  `        ``// if common String found then break as we are ` `        ``// considering index sums in increasing order. ` `        ``if` `(res.size() > ``0``)  ` `            ``break``; ` `    ``} ` ` `  `    ``// print the resultant list ` `    ``for` `(``int` `i = ``0``; i < res.size(); i++)  ` `        ``System.out.print(res.get(i)+``" "``); ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``// Creating list1 ` `    ``Vector list1 = ``new` `Vector<>(); ` `    ``list1.add(``"GeeksforGeeks"``); ` `    ``list1.add(``"Udemy"``); ` `    ``list1.add(``"Coursera"``); ` `    ``list1.add(``"edX"``); ` ` `  `    ``// Creating list2 ` `    ``Vector list2= ``new` `Vector<>(); ` `    ``list2.add(``"Codecademy"``); ` `    ``list2.add(``"Khan Academy"``); ` `    ``list2.add(``"GeeksforGeeks"``); ` ` `  `    ``find(list1, list2); ` ` `  `} ` `} ` ` `  `// This code contributed by Rajput-Ji `

Output:

```GeeksforGeeks
```

Time Complexity : O((l1+l2)2 *x), where l1 and l2 are the lengths of list1 and list2 respectively and x refers to string length.

Auxiliary Space : O(l*x), where x refers to length of resultant list and l is length of maximum size word.

Using Hash:

1. Traverse over the list1 and create an entry for index each element of list1 in a Hash Table.
2. Traverse over list2 and for every element, check if the same element already exists as a key in the map. If so, it means that the element exists in both the lists.
3. Find out the sum of indices corresponding to common element in the two lists. If this sum is lesser than the minimum sum obtained till now, update the resultant list.
4. If the sum is equal to the minimum sum obtained till now, put an extra entry corresponding to the element in list2 in the resultant list.
5.  `// Hashing based C++ program to find common elements ` `// with minimum index sum. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to print common strings with minimum index sum ` `void` `find(vector list1, vector list2) ` `{ ` `    ``// mapping strings to their indices ` `    ``unordered_map map;  ` `    ``for` `(``int` `i = 0; i < list1.size(); i++)  ` `        ``map[list1[i]] = i; ` ` `  `    ``vector res; ``// resultant list ` ` `  `    ``int` `minsum = INT_MAX; ` `    ``for` `(``int` `j = 0; j < list2.size(); j++)  ` `    ``{ ` `        ``if` `(map.count(list2[j]))  ` `        ``{ ` `            ``// If current sum is smaller than minsum ` `            ``int` `sum = j + map[list2[j]]; ` `            ``if` `(sum < minsum)  ` `            ``{ ` `                ``minsum = sum; ` `                ``res.clear(); ` `                ``res.push_back(list2[j]); ` `            ``}  ` ` `  `            ``// if index sum is same then put this  ` `            ``// string in resultant list as well   ` `            ``else` `if` `(sum == minsum)  ` `                ``res.push_back(list2[j]); ` `        ``} ` `    ``} ` ` `  `    ``// Print result ` `    ``for` `(``int` `i = 0; i < res.size(); i++)  ` `        ``cout << res[i] << ``" "``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``// Creating list1 ` `    ``vector list1; ` `    ``list1.push_back(``"GeeksforGeeks"``); ` `    ``list1.push_back(``"Udemy"``); ` `    ``list1.push_back(``"Coursera"``); ` `    ``list1.push_back(``"edX"``); ` ` `  `    ``// Creating list2 ` `    ``vector list2; ` `    ``list2.push_back(``"Codecademy"``); ` `    ``list2.push_back(``"Khan Academy"``); ` `    ``list2.push_back(``"GeeksforGeeks"``); ` ` `  `    ``find(list1, list2); ` `    ``return` `0; ` `} `

Output:

```GeeksforGeeks
```

Time Complexity : O(l1+l2), where l1 and l2 are the lengths of list1 and list2 respectively.

Auxiliary Space : O(l1*x), where x refers to length of resultant list and l is length of maximum size word.

## tags:

Hash Strings cpp-unordered_map Hash Strings