Minimum Index Sum of Two Lists

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:


Solution:

class Solution {
    static class Node {
        String s;
        int index;
        
        public Node(String s, int index) {
            this.s = s;
            this.index = index;
        }
    }
    
    public String[] findRestaurant(String[] list1, String[] list2) {
        List<Node> res = new ArrayList();
        Map<String, Node> map = new HashMap();
        for (int i = 0; i < list2.length; i ++) {
            String s = list2[i];
            map.put(s, new Node(s, i));
        }
        for (int i = 0; i < list1.length; i ++) {
            String s = list1[i];
            if (map.containsKey(s)) {
                Node r = map.get(s);
                r.index += i;
                res.add(r);
            }
        }
        Collections.sort(res, (a, b) -> Integer.compare(a.index, b.index));
        int max = res.get(0).index, idxToKeep = 0;
        for (int i = 1; i < res.size(); i ++) {
            if (res.get(i).index == max) {
                idxToKeep = i;
            } else {
                break;
            }
        }
        res.subList(idxToKeep + 1, res.size()).clear();
        String[] arr = new String[res.size()];
        for (int i = 0; i < arr.length; i ++) {
            arr[i] = res.get(i).s;
        }
        return arr;
    }
}