Store each restaurant from list1 in a hash map with its index. Then iterate through list2, and for each common restaurant, compute the index sum. Track the minimum index sum and collect all restaurants that match it.
Build hash maps for both lists, then iterate through the smaller map to find common restaurants. Collect results by minimum index sum in a second pass.
""" 0599.1 - Minimum Index Sum of Two Lists - Solution 1 - HashMap Lookup """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
"""Find Restaurant Function"""
index_map = {restaurant: i for i, restaurant in enumerate(list1)}
min_sum = float("inf")
result = []
for j, restaurant in enumerate(list2):
if restaurant in index_map:
index_sum = index_map[restaurant] + j
if index_sum < min_sum:
min_sum = index_sum
result = [restaurant]
elif index_sum == min_sum:
result.append(restaurant)
return result
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
)) # ["Shogun"]
print(Solution().findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["KFC", "Shogun", "Burger King"]
)) # ["Shogun"]
print(Solution().findRestaurant(
["happy", "sad", "good"],
["sad", "happy", "good"]
)) # ["sad", "happy"]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0599.2 - Minimum Index Sum of Two Lists - Solution 2 - Two-Pass HashMap """
#####################################################################################
# Imports
#####################################################################################
from typing import List
#####################################################################################
# Classes
#####################################################################################
class Solution:
"""Solution Class"""
def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
"""Find Restaurant Function"""
map1 = {r: i for i, r in enumerate(list1)}
map2 = {r: j for j, r in enumerate(list2)}
common = {}
for restaurant in map1:
if restaurant in map2:
common[restaurant] = map1[restaurant] + map2[restaurant]
if not common:
return []
min_sum = min(common.values())
return [r for r, s in common.items() if s == min_sum]
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
print(Solution().findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
)) # ["Shogun"]
print(Solution().findRestaurant(
["Shogun", "Tapioca Express", "Burger King", "KFC"],
["KFC", "Shogun", "Burger King"]
)) # ["Shogun"]
print(Solution().findRestaurant(
["happy", "sad", "good"],
["sad", "happy", "good"]
)) # ["sad", "happy"]
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()