Minimum Index Sum of Two Lists

Problem

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.

Example 1:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["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).

Note:

• The length of both lists will be in the range of [1, 1000].
• The length of strings in both lists will be in the range of [1, 30].
• The index is starting from 0 to the list length minus 1.
• No duplicates in both lists.

Solution

Linear time complexity

public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        String res = "";
        Map<String, Integer> map = new HashMap<>();
        int sumIndex = Integer.MAX_VALUE;
        for (int i = 0; i < list1.length; i++) map.put(list1[i], i);
        for (int i = 0; i < list2.length; i++) {
            String restName = list2[i];
            int tempSum = i + map.getOrDefault(restName, 0);
            if (map.containsKey(restName) && tempSum <= sumIndex) {
                res = tempSum < sumIndex ? restName : res + "," + restName;
                sumIndex = tempSum;
            }
        }
        return res.split(",");
    }
}

Analysis

We first loop the list1 to store its restName and index into our hashMap
Then we loop the list2, we get the tempSum and compare it with sumIndex
If we find smaller or equal one, we update the res and sumIndex
At the end, we return res.split(",") to convert res to String[]

Complexity

• Time: O(n), where n is the max length of list1 and list2
• Space: O(l1), where l1 is the length of list1, the size of hashMap won't exceed l1