Leetcode

Minimum Index Sum of Two Lists

May 26, 2022 by aAshish

  • 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