Question
Two array lists that have restaurant names are given. Then, you need to find a common restaurant name among lists. If some answer exists, you should choose the restaurant that has the minimum sum of those elements. If the minimum sum is also equal, return the list that contains all of them.
Just so you know, each array list does not have a duplicated restaurant name.
Solution
Firstly, we should check all elements of the first given array list and store it into a hashmap that key is restaurant name and value is the index of the elements. Then, explore all elements of the second given array list. If the restaurant name from the second one exists in the hashmap and the sum of the indices is smaller than the current minimum sum, create a new array list and insert the restaurant name. If the sum is as same as before, append it into the result array. In the end, return the result array.
Submittions
Here is the result of the submission in leetcode.
Time complexity: O(n+m)
Space complexity: O(n)
Runtime: 160 ms, faster than 55.70% of Python3 online submissions for Minimum Index Sum of Two Lists.
Memory Usage: 14.3 MB, less than 11.11% of Python3 online submissions for Minimum Index Sum of Two Lists.
Here is my python code.
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
interests: Dict[str, int] = {}
for i, r in enumerate(list1):
interests[r] = i
res: List[str] = []
minSum: float = float('inf')
for i, r in enumerate(list2):
if r not in interests:
continue
if interests[r] + i < minSum:
res = [r]
minSum = interests[r] + i
elif interests[r] + i == minSum:
res.append(r)
return res
https://github.com/nk18chi/leetcode/tree/master/solutions/minimum_indlex_sum_of_two_lists
If you change minSum: float = float('inf') to minSum: int = 2**31-1, the runtime must be faster. Technically, this might be wrong because int in python3 can be long type, which means that there is no restriction of the value of integers in python3 like a minimum and maximum.
However, sys.maxsize can be used as an integer larger than any practical list or string index. It conforms to the implementation’s “natural” integer size and is typically the same as sys.maxint in previous releases on the same platform (assuming the same build options).
