## Minimum Index Sum of Two Lists

• Time:O(m + n), where m = |\texttt{list1}| \cdot \max(|\texttt{list1[i]}|) and n = |\texttt{list2}| \cdot \max(|\texttt{list2[i]}|)
• Space:O(n)

## C++

class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string> ans;
unordered_map<string, int> restaurantToIndex;
int minSum = INT_MAX;

for (int i = 0; i < list1.size(); ++i)
restaurantToIndex[list1[i]] = i;

for (int i = 0; i < list2.size(); ++i) {
const string& restaurant = list2[i];
if (restaurantToIndex.count(restaurant)) {
const int sum = restaurantToIndex[restaurant] + i;
if (sum < minSum) {
minSum = sum;
ans = {restaurant};
} else if (sum == minSum) {
ans.push_back(restaurant);
}
}
}

return ans;
}
};


## JAVA

class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
List<String> ans = new LinkedList<>();
Map<String, Integer> restaurantToIndex = new HashMap<>();
int minSum = Integer.MAX_VALUE;

for (int i = 0; i < list1.length; ++i)
restaurantToIndex.put(list1[i], i);

for (int i = 0; i < list2.length; ++i) {
final String restaurant = list2[i];
if (restaurantToIndex.containsKey(restaurant)) {
final int sum = restaurantToIndex.get(restaurant) + i;
if (sum < minSum) {
minSum = sum;
ans.clear();
ans.add(restaurant);
} else if (sum == minSum) {
ans.add(restaurant);
}
}
}

return ans.toArray(new String[0]);
}
}


## Python

class Solution:
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
ans = []
restaurantToIndex = {restaurant: i for i,
restaurant in enumerate(list1)}
minSum = math.inf

for i, restaurant in enumerate(list2):
if restaurant in restaurantToIndex:
sum = restaurantToIndex[restaurant] + i
if sum < minSum:
ans.clear()
if sum <= minSum:
ans.append(restaurant)
minSum = sum

return ans