Given two arrays of strings list1 and list2, find the common strings with the least index sum.
A common string is a string that appeared in both list1 and list2.
A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.
Return all the common strings with the least index sum. Return the answer in any order.
Example 1:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"] Output: ["Shogun"] Explanation: The only common string is "Shogun".
Example 2:
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"] Output: ["Shogun"] Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.
Example 3:
Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"] Output: ["sad","happy"] Explanation: There are three common strings: "happy" with index sum = (0 + 1) = 1. "sad" with index sum = (1 + 0) = 1. "good" with index sum = (2 + 2) = 4. The strings with the least index sum are "sad" and "happy".
Constraints:
1 <= list1.length, list2.length <= 10001 <= list1[i].length, list2[i].length <= 30list1[i] and list2[i] consist of spaces ' ' and English letters.list1 are unique.list2 are unique.list1 and list2.To solve #599 Minimum Index Sum of Two Lists, the goal is to find common strings between two lists where the sum of their indices is minimal. A brute-force approach would compare every element of the first list with every element of the second, but this results in unnecessary repeated checks.
A more efficient method uses a hash table. First, store each string from the first list in a hash map with its index as the value. Then iterate through the second list and check whether each string exists in the map. If it does, compute the index sum and keep track of the smallest sum encountered. Maintain a result list to store all strings that match this minimum index sum.
This approach significantly reduces lookup time thanks to constant-time hash map access. The algorithm runs in O(n + m) time where n and m are the lengths of the two lists, while using O(n) extra space for the hash table.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table (Store first list indices and scan second list) | O(n + m) | O(n) |
NeetCodeIO
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 =
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar problems involving hash maps, string matching, and index tracking are common in FAANG-style interviews. It tests your ability to optimize brute-force comparisons using hashing.
A hash table (hash map) is the best data structure for this problem. It allows constant-time lookups when checking whether a string from the second list appears in the first list.
Yes, it can be solved using nested loops that compare every pair of strings from the two lists. However, this approach has O(n × m) time complexity, which is less efficient than the hash map solution.
The optimal approach uses a hash table to store the index of each string from the first list. While scanning the second list, you check for matches and compute the index sum, keeping track of the minimum. This reduces the overall complexity to linear time.
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.