599. Minimum Index Sum of Two Lists

Problem Description

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 minimal.

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

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 common string is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun","KFC"]
Explanation: The common strings with the least index sum are "Shogun" with index sum = (0 + 1) = 1 and "KFC" with index sum = (3 + 0) = 3.

Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1
"sad" with index sum = (1 + 0) = 1
"good" with index sum = (2 + 2) = 4
The strings with the least index sum are "sad" and "happy".

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.

Python Solution

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        index_map = {s: i for i, s in enumerate(list1)}
        min_sum = float('inf')
        result = []
        
        for j, s in enumerate(list2):
            if s in index_map:
                i = index_map[s]
                if i + j < min_sum:
                    min_sum = i + j
                    result = [s]
                elif i + j == min_sum:
                    result.append(s)
                    
        return result

Java Solution

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map indexMap = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            indexMap.put(list1[i], i);
        }
        
        List result = new ArrayList<>();
        int minSum = Integer.MAX_VALUE;
        
        for (int j = 0; j < list2.length; j++) {
            if (indexMap.containsKey(list2[j])) {
                int i = indexMap.get(list2[j]);
                if (i + j < minSum) {
                    minSum = i + j;
                    result.clear();
                    result.add(list2[j]);
                } else if (i + j == minSum) {
                    result.add(list2[j]);
                }
            }
        }
        
        return result.toArray(new String[0]);
    }
}

C++ Solution

class Solution {
public:
    vector findRestaurant(vector& list1, vector& list2) {
        unordered_map indexMap;
        for (int i = 0; i < list1.size(); i++) {
            indexMap[list1[i]] = i;
        }
        
        vector result;
        int minSum = INT_MAX;
        
        for (int j = 0; j < list2.size(); j++) {
            if (indexMap.count(list2[j])) {
                int i = indexMap[list2[j]];
                if (i + j < minSum) {
                    minSum = i + j;
                    result = {list2[j]};
                } else if (i + j == minSum) {
                    result.push_back(list2[j]);
                }
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function(list1, list2) {
    const indexMap = new Map();
    for (let i = 0; i < list1.length; i++) {
        indexMap.set(list1[i], i);
    }
    
    let result = [];
    let minSum = Infinity;
    
    for (let j = 0; j < list2.length; j++) {
        if (indexMap.has(list2[j])) {
            const i = indexMap.get(list2[j]);
            if (i + j < minSum) {
                minSum = i + j;
                result = [list2[j]];
            } else if (i + j === minSum) {
                result.push(list2[j]);
            }
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    public string[] FindRestaurant(string[] list1, string[] list2) {
        var indexMap = new Dictionary();
        for (int i = 0; i < list1.Length; i++) {
            indexMap[list1[i]] = i;
        }
        
        var result = new List();
        int minSum = int.MaxValue;
        
        for (int j = 0; j < list2.Length; j++) {
            if (indexMap.ContainsKey(list2[j])) {
                int i = indexMap[list2[j]];
                if (i + j < minSum) {
                    minSum = i + j;
                    result.Clear();
                    result.Add(list2[j]);
                } else if (i + j == minSum) {
                    result.Add(list2[j]);
                }
            }
        }
        
        return result.ToArray();
    }
}