Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map.Entry;
/*
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:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
Example 2:
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["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).
Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.
*/
public class Minimum_Index_Sum_of_Two_Lists {
public static void main(String[] args) {
Minimum_Index_Sum_of_Two_Lists out = new Minimum_Index_Sum_of_Two_Lists();
Solution s = out.new Solution();
String[] s1 = new String[]{"Shogun","Tapioca Express","Burger King","KFC"};
String[] s2 = new String[]{"KFC","Burger King","Tapioca Express","Shogun"};
System.out.println(Arrays.toString(s.findRestaurant(s1, s2)));
Solution2 sl2 = out.new Solution2();
String[] s21 = new String[]{"Shogun","Tapioca Express","Burger King","KFC"};
String[] s22 = new String[]{"KFC","Burger King","Tapioca Express","Shogun"};
System.out.println(Arrays.toString(sl2.findRestaurant(s21, s22)));
}
// o(n^2)
public class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
if (list1 == null || list2 == null || list1.length == 0 || list2.length == 0) {
return new String[]{""};
}
// maintain 2 indexes, both pointing to the same restaurant
int index1 = -1; // minus: not-found
int index2 = -1;
int min = Integer.MAX_VALUE;
ArrayList<String> restaurant = new ArrayList<String>(30); // length of strings 1-30
for (int i = 0; i < list1.length; i++) {
for (int j = 0; j < list2.length; j++) {
if (list1[i].equals(list2[j]) && (i + j < min)) {
// record indexes
min = i + j;
restaurant = new ArrayList<String>(30);
restaurant.add(list1[i]);
} else if (list1[i].equals(list2[j]) && (i + j == min)) {
// choice tie, then print all of them
restaurant.add(list1[i]);
}
}
}
return restaurant.toArray(new String[restaurant.size()]);
// @note: below has runtime error: java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
//return (String[]) restaurant.toArray();
}
}
// o(m+n), extra space
public class Solution2 {
public String[] findRestaurant(String[] list1, String[] list2) {
if (list1 == null || list2 == null || list1.length == 0 || list2.length == 0) {
return new String[]{""};
}
// maintain 2 indexes, both pointing to the same restaurant
int index1 = -1; // minus: not-found
int index2 = -1;
int min = Integer.MAX_VALUE;
ArrayList<String> restaurant = new ArrayList<String>(30); // length of strings 1-30
// @note: use 2 hashmap: 1.store name => index, 2.store sumIndex => word
// store list1 for o(1) access
HashMap<String, Integer> hmList1 = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
hmList1.put(list1[i], i);
}
// store sumIndex => word
int minIndex = Integer.MAX_VALUE;
for (int j = 0; j < list2.length; j++) {
if (hmList1.containsKey(list2[j])) {
// common interest
int sum = j + hmList1.get(list2[j]);
if (sum < minIndex) {
minIndex = sum; // update minIndex
restaurant = new ArrayList<String>(30);
restaurant.add(list2[j]);
} else if (sum == minIndex) {
restaurant.add(list2[j]);
}
}
}
return restaurant.toArray(new String[restaurant.size()]);
}
}
}
Java
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
int length1 = list1.length, length2 = list2.length;
int leastIndexSum = Integer.MAX_VALUE;
Map<String, Integer> list1Map = new HashMap<String, Integer>();
Map<Integer, List<String>> indexSumInterestMap = new HashMap<Integer, List<String>>();
for (int i = 0; i < length1; i++)
list1Map.put(list1[i], i);
for (int i = 0; i < length2; i++) {
String interest = list2[i];
if (!list1Map.containsKey(interest))
continue;
int indexSum = list1Map.get(interest) + i;
List<String> interests = indexSumInterestMap.getOrDefault(indexSum, new ArrayList<String>());
interests.add(interest);
indexSumInterestMap.put(indexSum, interests);
if (indexSum < leastIndexSum)
leastIndexSum = indexSum;
}
List<String> interestsList = indexSumInterestMap.getOrDefault(leastIndexSum, new ArrayList<String>());
int length = interestsList.size();
String[] interests = new String[length];
for (int i = 0; i < length; i++)
interests[i] = interestsList.get(i);
return interests;
}
}