0599. Minimum Index Sum of Two Lists

https://leetcode.com/problems/minimum-index-sum-of-two-lists

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.

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"]

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.

ac

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        // edge cases
        if (list1.length == 0 || list2.length == 0) return new String[0];
        if (list1.length < list2.length) return findRestaurant(list2, list1); // save some space

        // list2 add to map
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < list2.length; i++) {
            map.put(list2[i], i);
        }

        // iterate list1, get indices sum
        List<String> res = new ArrayList<>();
        int minSum = Integer.MAX_VALUE;
        for (int i = 0; i < list1.length; i++) {
            if (map.containsKey(list1[i])) {
                int currSum = i + map.get(list1[i]);
                if (currSum <= minSum) {
                    if (currSum < minSum) res = new ArrayList<>(); // reset
                    res.add(list1[i]);
                    minSum = currSum;
                }
            }
        }

        // list to array
        String[] ans = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }

        return ans;
    }
}