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.
1function findIndexSum(list1, list2) {
2 const map = new Map();
3 list1.forEach((item, index) => map.set(item, index));
4
5 let minSum = Infinity;
6 const result = [];
7
8 list2.forEach((item, index) => {
9 if (map.has(item)) {
10 const sum = index + map.get(item);
11 if (sum < minSum) {
12 result.length = 0;
13 result.push(item);
14 minSum = sum;
15 } else if (sum === minSum) {
16 result.push(item);
17 }
18 }
19 });
20
21 return result;
22}
23
24const list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"];
25const list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"];
26console.log(findIndexSum(list1, list2));This JavaScript solution leverages the use of a Map to manage indices of strings from list1. It checks list2 using the map for common elements and optimally computes the index sums to find the minimums.
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.