Algorithm
Problem Name: 599. Minimum Index Sum of Two Lists
Problem Link: https://leetcode.com/problems/minimum-index-sum-of-two-lists/
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 the minimum value among all the other common strings.
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"] Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.
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 <= 10001 <= list1[i].length, list2[i].length <= 30list1[i]andlist2[i]consist of spaces' 'and English letters.- All the strings of
list1are unique. - All the strings of
list2are unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string>res;
unordered_map < string, int>m;
int min = INT_MAX;
for (int i = 0; i < list1.size(); i++) m[list1[i]] = i;
for (int i = 0; i < list2.size(); i++)
if (m.count(list2[i]) != 0)
if (m[list2[i]] + i < min) min = m[list2[i]] + i, res.clear(), res.push_back(list2[i]);
else if (m[list2[i]] + i == min) res.push_back(list2[i]);
return res;
}
};
Input
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output
["Shogun"]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map map = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
int minIndexSum = Integer.MAX_VALUE;
Map < String, Integer> stringToIndexSum = new HashMap<>();
for (int i = 0; i < list2.length; i++) {
if (map.containsKey(list2[i])) {
int indexSum = i + map.get(list2[i]);
minIndexSum = Math.min(minIndexSum, indexSum);
stringToIndexSum.put(list2[i], indexSum);
}
}
List < String> result = new ArrayList<>();
for (String key : stringToIndexSum.keySet()) {
if (stringToIndexSum.get(key) == minIndexSum) {
result.add(key);
}
}
String[] resultArr = new String[result.size()];
for (int i = 0; i < result.size(); i++) {
resultArr[i] = result.get(i);
}
return resultArr;
}
}
Input
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output
["Shogun"]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findRestaurant = function(list1, list2) {
const hash = {};
for (let i = 0; i < list1.length; i++) {
if (!hash.hasOwnProperty(list1[i])) {
hash[list1[i]] = i;
}
}
const resArr = [];
for (let j = 0; j < list2.length; j++) {
if (hash.hasOwnProperty(list2[j])) {
resArr.push([list2[j], hash[list2[j]] + j]);
}
}
const resHash = {};
resArr.forEach(el => {
if (resHash.hasOwnProperty(el[1])) {
resHash[el[1]].push(el[0]);
} else {
resHash[el[1]] = [el[0]];
}
});
resArr.sort((a, b) => a[1] - b[1]);
return resHash[resArr[0][1]];
};
console.log(
findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["KFC", "Burger King", "Tapioca Express", "Shogun"]
)
);
Input
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output
["Shogun"]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findRestaurant(self, list1, list2):
"""
:type list1: List[str]
:type list2: List[str]
:rtype: List[str]
"""
dic={}
for item1 in list1:
for item2 in list2:
if item1==item2:
dic[item1]=list1.index(item1)+list2.index(item2)
return [k for k in dic if dic[k]==min(dic.values())]
Input
list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output
["Shogun"]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0599_MinimumIndexSumOfTwoLists
{
public string[] FindRestaurant(string[] list1, string[] list2)
{
if (list1.Length > list2.Length) return FindRestaurant(list2, list1);
var map = new Dictionary < string, int>();
for (int i = 0; i < list1.Length; i++)
map[list1[i]] = i;
var result = new List < string>();
var sum = int.MaxValue;
for (int i = 0; i < list2.Length; i++)
{
if (!map.ContainsKey(list2[i]))
continue;
var cur = map[list2[i]] + i;
if (cur < sum)
{
sum = cur;
result.Clear();
result.Add(list2[i]);
}
else if (cur == sum)
result.Add(list2[i]);
}
return result.ToArray();
}
}
}
Input
list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output
["sad","happy"]