## Algorithm

Problem Name: 599. Minimum Index Sum of Two Lists

Given two arrays of strings `list1` and `list2`, find the common strings with the least index sum.

A common string is a string that appeared in both `list1` and `list2`.

A common string with the least index sum is a common string such that if it appeared at `list1[i]` and `list2[j]` then `i + j` should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Example 1:

```Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
```

Example 2:

```Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.
```

Example 3:

```Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".
```

Constraints:

• `1 <= list1.length, list2.length <= 1000`
• `1 <= list1[i].length, list2[i].length <= 30`
• `list1[i]` and `list2[i]` consist of spaces `' '` and English letters.
• All the strings of `list1` are unique.
• All the strings of `list2` are unique.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string>res;
unordered_map < string, int>m;
int min = INT_MAX;
for (int i = 0; i  <  list1.size(); i++) m[list1[i]] = i;
for (int i = 0; i  <  list2.size(); i++)
if (m.count(list2[i]) != 0)
if (m[list2[i]] + i < min) min = m[list2[i]] + i, res.clear(), res.push_back(list2[i]);
else if (m[list2[i]] + i == min) res.push_back(list2[i]);
return res;
}
};
``````
Copy The Code &

Input

cmd
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output

cmd
["Shogun"]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map map = new HashMap<>();
for (int i = 0; i  <  list1.length; i++) {
map.put(list1[i], i);
}
int minIndexSum = Integer.MAX_VALUE;
Map < String, Integer> stringToIndexSum = new HashMap<>();
for (int i = 0; i  <  list2.length; i++) {
if (map.containsKey(list2[i])) {
int indexSum = i + map.get(list2[i]);
minIndexSum = Math.min(minIndexSum, indexSum);
stringToIndexSum.put(list2[i], indexSum);
}
}
List < String> result = new ArrayList<>();
for (String key : stringToIndexSum.keySet()) {
if (stringToIndexSum.get(key) == minIndexSum) {
result.add(key);
}
}
String[] resultArr = new String[result.size()];
for (int i = 0; i  <  result.size(); i++) {
resultArr[i] = result.get(i);
}
return resultArr;
}
}
``````
Copy The Code &

Input

cmd
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output

cmd
["Shogun"]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findRestaurant = function(list1, list2) {
const hash = {};
for (let i = 0; i  <  list1.length; i++) {
if (!hash.hasOwnProperty(list1[i])) {
hash[list1[i]] = i;
}
}
const resArr = [];
for (let j = 0; j  <  list2.length; j++) {
if (hash.hasOwnProperty(list2[j])) {
resArr.push([list2[j], hash[list2[j]] + j]);
}
}
const resHash = {};
resArr.forEach(el => {
if (resHash.hasOwnProperty(el[1])) {
resHash[el[1]].push(el[0]);
} else {
resHash[el[1]] = [el[0]];
}
});
resArr.sort((a, b) => a[1] - b[1]);
return resHash[resArr[0][1]];
};

console.log(
findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["KFC", "Burger King", "Tapioca Express", "Shogun"]
)
);
``````
Copy The Code &

Input

cmd
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]

Output

cmd
["Shogun"]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
dic={}
for item1 in list1:
for item2 in list2:
if item1==item2:
dic[item1]=list1.index(item1)+list2.index(item2)
return [k for k in dic if dic[k]==min(dic.values())]
``````
Copy The Code &

Input

cmd
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]

Output

cmd
["Shogun"]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0599_MinimumIndexSumOfTwoLists
{
public string[] FindRestaurant(string[] list1, string[] list2)
{
if (list1.Length > list2.Length) return FindRestaurant(list2, list1);

var map = new Dictionary < string, int>();
for (int i = 0; i  <  list1.Length; i++)
map[list1[i]] = i;

var result = new List < string>();
var sum = int.MaxValue;
for (int i = 0; i  <  list2.Length; i++)
{
if (!map.ContainsKey(list2[i]))
continue;

var cur = map[list2[i]] + i;
if (cur  <  sum)
{
sum = cur;
result.Clear();
result.Add(list2[i]);
}
else if (cur == sum)
result.Add(list2[i]);
}

return result.ToArray();
}
}
}
``````
Copy The Code &

Input

cmd
list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]

Output

cmd
["sad","happy"]
Advertisements