599. Minimum Index Sum of Two Lists

1. Description

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.
You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

2. Example

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 restaurant they both like is “Shogun”.

Example 2:
Input: list1 = [“Shogun”,“Tapioca Express”,“Burger King”,“KFC”], list2 = [“KFC”,“Shogun”,“Burger King”] Output: [“Shogun”]
Explanation: The restaurant they both like and have the least index sum is “Shogun” with index sum 1 (0+1).

Example 3:
Input: list1 = [“Shogun”,“Tapioca Express”,“Burger King”,“KFC”], list2 = [“KFC”,“Burger King”,“Tapioca Express”,“Shogun”]
Output: [“KFC”,“Burger King”,“Tapioca Express”,“Shogun”]

Example 4:
Input: list1 = [“Shogun”,“Tapioca Express”,“Burger King”,“KFC”], list2 = [“KNN”,“KFC”,“Burger King”,“Tapioca Express”,“Shogun”]
Output: [“KFC”,“Burger King”,“Tapioca Express”,“Shogun”]

Example 5:
Input: list1 = [“KFC”], list2 = [“KFC”]
Output: [“KFC”]

3. 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 stings of list1 are unique.
• All the stings of list2 are unique.

4. Solutions

My Accepted Solution

m = i_list1.size(), n = i_list2.size()
Time complexity: O(m + n)
Space complexity: O(m)

class Solution 
{
public:
    // vector<string> findRestaurant(vector<string>& list1, vector<string>& list2)
    vector<string> findRestaurant(vector<string> &i_list1, vector<string> &i_list2) 
    {
        unordered_map<string, int> strInList1Index;
        for(int i = 0; i < i_list1.size(); i++)
            strInList1Index[i_list1[i]] = i;
        
        vector<string> result;
        int leastIndexSum = INT_MAX;
        for(int i = 0; i < i_list2.size(); i++)
        {
            if(strInList1Index.find(i_list2[i]) == strInList1Index.end()) continue;
            
            if(i + strInList1Index[i_list2[i]] < leastIndexSum)
            {
                result = {i_list2[i]};
                leastIndexSum = i + strInList1Index[i_list2[i]];
            }
            else if(i + strInList1Index[i_list2[i]] == leastIndexSum)
            {
                result.push_back(i_list2[i]);
            }
        }
        
        return result;
    }
};