Skip to content

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)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 (const auto it = restaurantToIndex.find(restaurant);
          it != restaurantToIndex.cend()) {
        const int sum = it->second + i;
        if (sum < minSum) {
          minSum = sum;
          ans = {restaurant};
        } else if (sum == minSum) {
          ans.push_back(restaurant);
        }
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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]);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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