Minimum Index Sum of Two Lists

Problem

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

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 strings of list1 are unique.
• All the strings of list2 are unique.
• There is at least a common string between list1 and list2.

Solution

The problem Minimum Index Sum of Two Lists can be solved by creating a hash map of strings from one list and checking if strings in the other list exists in the hash map.

Implementation

class Solution
{
  public:
    vector<string> findRestaurant(vector<string> &list1, vector<string> &list2)
    {
        if (list1.size() > list2.size())
            list1.swap(list2);

        unordered_map<string, int> hashmap;
        for (int i = 0; i < list1.size(); i++)
            hashmap[list1[i]] = i;

        int min_idx = INT_MAX;
        vector<string> ret;

        for (int i = 0; i < list2.size(); i++)
            if (hashmap.find(list2[i]) != hashmap.end())
                if (min_idx >= i + hashmap[list2[i]])
                {
                    if (min_idx > i + hashmap[list2[i]])
                    {
                        min_idx = i + hashmap[list2[i]];
                        ret.clear();
                    }
                    ret.push_back(list2[i]);
                }

        return ret;
    }
};