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 <stdio.h>
2#include <string.h>
3#include <stdlib.h>
4
5#define MAX_LENGTH 30
6#define MAX_SIZE 1000
7
8int* findIndexSum(char* list1[], int size1, char* list2[], int size2, int* returnSize) {
9 char* hashmap[MAX_SIZE];
10 int index_map[MAX_SIZE];
11 int min_sum = 2000; // Initialize with a large number
12 for (int i = 0; i < size1; ++i) {
13 hashmap[i] = list1[i];
14 index_map[i] = i;
15 }
16
17 char** result = malloc(size2 * sizeof(char*));
18 int resultIndex = 0;
19
20 for (int j = 0; j < size2; ++j) {
21 for (int k = 0; k < size1; ++k) {
22 if (strcmp(list2[j], hashmap[k]) == 0) {
23 int sum = j + index_map[k];
24 if (sum < min_sum) {
25 resultIndex = 0;
26 result[resultIndex++] = hashmap[k];
27 min_sum = sum;
28 } else if (sum == min_sum) {
29 result[resultIndex++] = hashmap[k];
30 }
31 break;
32 }
33 }
34 }
35
36 *returnSize = resultIndex;
37 return result;
38}
39
40int main() {
41 int returnSize = 0;
42 char* list1[] = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
43 char* list2[] = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
44
45 int size1 = sizeof(list1) / sizeof(list1[0]);
46 int size2 = sizeof(list2) / sizeof(list2[0]);
47
48 char** result = findIndexSum(list1, size1, list2, size2, &returnSize);
49
50 for (int i = 0; i < returnSize; ++i) {
51 printf("%s\n", result[i]);
52 }
53
54 free(result);
55}This solution iterates through the first list and stores each string with its index in hashmap and index_map. It then iterates through the second list, checking if each element is in the hashmap. It computes the index sum and records the result if it is the minimum found so far.
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.