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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4
5using namespace std;
6
7vector<string> findIndexSum(vector<string>& list1, vector<string>& list2) {
8 unordered_map<string, int> indexMap;
9 for (int i = 0; i < list1.size(); ++i) {
10 indexMap[list1[i]] = i;
11 }
12
13 vector<string> result;
14 int minSum = INT_MAX;
15
16 for (int j = 0; j < list2.size(); ++j) {
17 if (indexMap.find(list2[j]) != indexMap.end()) {
18 int sum = j + indexMap[list2[j]];
19 if (sum < minSum) {
20 result.clear();
21 result.push_back(list2[j]);
22 minSum = sum;
23 } else if (sum == minSum) {
24 result.push_back(list2[j]);
25 }
26 }
27 }
28
29 return result;
30}
31
32int main() {
33 vector<string> list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
34 vector<string> list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
35
36 vector<string> result = findIndexSum(list1, list2);
37 for (const auto& str : result) {
38 cout << str << endl;
39 }
40
41 return 0;
42}This C++ solution uses the unordered_map from the STL to store indices of elements from list1. We iterate through list2, checking for common elements and computing the index sum accordingly.
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.