# Minimum Index Sum of Two Lists

• Share my Swift solution - O(max(m, n)) time and O(max(m, n)) space using HashMap

``````class Solution599 {
func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
if list1.count == 0 || list2.count == 0 {
return []
}

var map = [String: Int]()
var minSum = Int.max
var result = [String]()

for i in 0..<list1.count {
map[list1[i]] = i
}
for i in 0..<list2.count {
if let item = map[list2[i]] {
let indexSum = i + item
if indexSum < minSum {
minSum = min(minSum, indexSum)
result.removeAll()
result.append(list2[i])
} else if indexSum == minSum {
result.append(list2[i])
}
}
}

return result
}
}
``````

• @cloud.runner Thanks for sharing your solution. For now I have added the code. Soon I will add the explanation and animation.

• Share My Simpler Solution.

public static String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> map1 = new HashMap<>();
Map<String, Integer> map2 = new HashMap<>();
Map<Integer, List<String>> result = new TreeMap<>();

``````    for (int i = 0; i < list1.length; i++) {
map1.put(list1[i], i);
}

for (int i = 0; i < list2.length; i++) {
map2.put(list2[i], i);
}

for (String key : map1.keySet()) {
if (map2.containsKey(key)) {
int sum = map1.get(key) + map2.get(key);
if (!result.containsKey(sum)) {
result.put(sum, new ArrayList<String>() {{
}});
} else {
}
}
}

Map.Entry<Integer, List<String>> entry = result.entrySet().iterator().next();

return entry.getValue().toArray(new String[entry.getValue().size()]);
}``````

• ``````public static String[] findRestaurant2(String[] list1, String[] list2) {
Map<String, Integer> map1 = new HashMap<>();
Map<String, Integer> map2 = new HashMap<>();
Map<Integer, List<String>> result = new TreeMap<>();

for (int i = 0; i < list1.length; i++) {
map1.put(list1[i], i);
}

for (int i = 0; i < list2.length; i++) {
map2.put(list2[i], i);
}

for (String key : map1.keySet()) {
if (map2.containsKey(key)) {
int sum = map1.get(key) + map2.get(key);
if (!result.containsKey(sum)) {
result.put(sum, new ArrayList<String>() {{
}});
} else {
}
}
}

Map.Entry<Integer, List<String>> entry = result.entrySet().iterator().next();

return entry.getValue().toArray(new String[entry.getValue().size()]);
}
``````

• System.out.println(findRestaurant(new String[]{"Shogun","Tapioca Express","Burger King","KFC"}, new String[]{"KNN","KFC","Burger King","Tapioca Express","Shogun"}));
failed with 3rd solution.

• @acarora According to me 3rd solution is giving right answer for your test case. How it is failing?

• @vinod23 yes it worked but i had kinda similar solution and was failing on that test case. but minor changes made it work. sorry for the confusion.

• @Vinod23 @compton_scatter We can make it more better.

While iterating over through List2 if i'th index is greater than minSum than we can simply break the loop

• @ruchit_tushar Thanks for your suggestion. I have updated the code.

• @ruchit_tushar agree.
Through all the solutions, it either creates a map for whole list1 or list2.
However, if the two lists are:
(A G B E C) and (B E X Y Z)

You'll soon find 'B' is the answer with minimum index sum 2;
You don't need to traverse either one of the whole list and make a hash.

@vinod23 as well.

Share my ruby solution(although it looks like duplicate, could be simper, but I think it beats all the creating Hash with a whole list solution)

The basic idea is to keep two indexes to track both list1 and list2; the index limitation could change if we get one index sum for one same pair of strings.

``````def find_restaurant(list1, list2)
min_index_sum = nil
restaurants = []
choices_hash = {}

limit1, limit2 = list1.length - 1, list2.length - 1
index1, index2 = 0, 0

while index1 <= limit1 || index2 <= limit2
if index1 <= limit1
if choices_hash.has_key?(list1[index1])
val = choices_hash[list1[index1]] + index1
choices_hash[list1[index1]] = val

if min_index_sum.nil? || min_index_sum > val
min_index_sum = val
restaurants = [list1[index1]]
elsif min_index_sum == val
restaurants << list1[index1]
end

limit1 = min_index_sum if limit1 > min_index_sum
limit2 = min_index_sum if limit2 > min_index_sum
else
choices_hash[list1[index1]] = index1
end

index1 += 1
end

if index2 <= limit2
if choices_hash.has_key?(list2[index2])
val = choices_hash[list2[index2]] + index2
choices_hash[list2[index2]] = val

if min_index_sum.nil? || min_index_sum > val
min_index_sum = val
restaurants = [list2[index2]]
elsif min_index_sum == val
restaurants << list2[index2]
end

limit1 = min_index_sum if limit1 > min_index_sum
limit2 = min_index_sum if limit2 > min_index_sum
else
choices_hash[list2[index2]] = index2
end

index2 += 1
end
end

restaurants
end
``````

class Solution(object):
def findRestaurant(self, list1, list2):
dict = {}
list = []
element = 0
minsum = 2147483647
for i in range(0,len(list2)):
if list2[i] not in dict:
dict[list2[i]] = i

``````    for i in range(0,len(list1)):
if list1[i] in dict:
tempsum = i + dict[list1[i]]
if minsum > tempsum:
minsum = tempsum
element = i
if len(list) is not 0:
list.pop()
list.append(list1[element])
elif minsum == tempsum:
element = i
list.append(list1[element])
return list``````

• ``````class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String,Integer> map = new HashMap<>();
int min = Integer.MAX_VALUE;
for (int i=0;i<list1.length;i++){
map.put(list1[i],i);
}

for (int j=0;j<list2.length;j++)
{
Integer temp = map.get(list2[j]);
if (temp!=null){
System.out.println("Temp is not null");
int sum = temp+j;
if (sum<=min){
if (sum==min){
}
min = sum;
}
}
}
``` def common_word_with_index(list1, list2): runners = list1 static = list2 dict_index = {} priority = -1 # Get which list have more words, and run for loop with this if len(list2) > len(list1): runners = list2 static = list1 # Create dictionary with same words in both list and assign key (index sum) and value (word) for run in runners: if run in static: index = static.index(run) + runners.index(run) dict_index.update({index:run}) # Get the word with least index value, to get the restaurant with least index value for key, val in dict_index.iteritems(): if priority == -1: priority = key if key <= priority: priority = key print(dict_index.get(priority)) common_word_with_index(["Shogun", "Tapioca Express","KFC", "Burger King"], ["Piatti", "The Grill at Torrey Pines", "KFC","Hungry Hunter Steakhouse", "Shogun","holyland"]) ```