Sponsored
Sponsored
This approach uses a hash map to store the indices of the elements from the first list. By iterating through the second list, we can check for common strings and calculate the minimum index sum efficiently.
Time Complexity: O(n * m) where n is the size of list1 and m is the size of list2. Space Complexity: O(n) for hash map storage.
1def findIndexSum(list1, list2):
2 index_map = {s: i for i, s in enumerate(list1)}
3 min_sum = float('inf')
4 result = []
5
6 for j, s in enumerate(list2):
7 if s in index_map:
8 i = index_map[s]
9 sum_index = i + j
10 if sum_index < min_sum:
11 min_sum = sum_index
12 result = [s]
13 elif sum_index == min_sum:
14 result.append(s)
15
16 return result
17
18list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
19list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
20print(findIndexSum(list1, list2))In this Python solution, we use a dictionary to store indices from list1. Then, we iterate over list2, checking for common elements and calculating the index sum, thereby determining the list with minimum index sum efficiently.
This approach uses two pointers to traverse both lists simultaneously. This can be useful in certain scenarios where both lists are already sorted in some order.
Time Complexity: O(n log n + m log m) due to sorting, where n is the size of list1 and m is the size of list2. Space Complexity: O(n + m) for storing sorted lists.
1def findIndexSumTwoPointer(list1, list2):
2 i = j = 0
3 min_sum =
In this Python solution, we first sort both lists by their string values while storing their original indexes. Then we simultaneously traverse both sorted lists using two pointers to find common elements, calculate their index sums, and determine the minimum sums.