# 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

```java
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;
    }
}
```