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.
1import java.util.*;
2
3public class Solution {
4 public String[] findIndexSum(String[] list1, String[] list2) {
5 Map<String, Integer> map = new HashMap<>();
6 for (int i = 0; i < list1.length; i++) {
7 map.put(list1[i], i);
8 }
9
10 List<String> result = new ArrayList<>();
11 int minSum = Integer.MAX_VALUE;
12
13 for (int j = 0; j < list2.length; j++) {
14 if (map.containsKey(list2[j])) {
15 int sum = j + map.get(list2[j]);
16 if (sum < minSum) {
17 result.clear();
18 result.add(list2[j]);
19 minSum = sum;
20 } else if (sum == minSum) {
21 result.add(list2[j]);
22 }
23 }
24 }
25
26 return result.toArray(new String[result.size()]);
27 }
28
29 public static void main(String[] args) {
30 Solution solution = new Solution();
31 String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
32 String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
33
34 String[] result = solution.findIndexSum(list1, list2);
35 System.out.println(Arrays.toString(result));
36 }
37}This Java solution uses a HashMap to store the indices of strings from list1. As we check strings in list2, we calculate the index sum for common strings. If we find a new minimum, we clear previous results and store the new minimum.
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.