LeetCode Solutions
599. 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)$
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;
}
};
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]);
}
}
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:
summ = restaurantToIndex[restaurant] + i
if summ < minSum:
ans.clear()
if summ <= minSum:
ans.append(restaurant)
minSum = summ
return ans