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.Problem Overview: You get two string arrays representing favorite restaurants from two people. The task is to return the restaurant(s) that appear in both lists with the smallest possible index sum i + j. If multiple restaurants share the same minimum sum, return all of them.
Approach 1: Hash Map Approach (O(n + m) time, O(n) space)
This is the standard solution using a hash table. First iterate through list1 and store each restaurant with its index in a hash map. Then iterate through list2. For every restaurant, check if it exists in the map using an O(1) lookup. If it exists, compute the index sum i + j. Track the smallest sum seen so far and update the result list accordingly. If a new smaller sum appears, clear the result and add the new restaurant; if the sum ties with the minimum, append it.
The key insight is constant‑time membership checking. Instead of comparing every pair of restaurants, you reduce the search to direct hash lookups. This turns a potential O(n*m) comparison into a linear scan. The approach works well for typical array intersection problems where fast membership checks are required.
Approach 2: Two Pointer / Incremental Index Scan (O(n^2) worst case, O(1) extra space)
This approach avoids extra data structures and instead scans both lists using increasing index sums. Start with sum = 0 and check all index pairs where i + j = sum. For each pair, compare the restaurant names directly. As soon as you find matches, record them. Once matches appear for a particular sum, you can stop because any later sums will be larger.
The technique behaves like a diagonal traversal over the conceptual matrix of index pairs. It is simple and uses constant extra space, relying only on string comparisons between the two lists. However, because comparisons may still grow quadratically in the worst case, it is less efficient for large inputs. Still, for short lists or environments where extra memory is restricted, it can be acceptable.
Since restaurant names are strings, equality checks are direct string comparisons. The main optimization comes from minimizing unnecessary comparisons or lookups.
Recommended for interviews: The hash map approach is what interviewers expect. It demonstrates recognition of a classic pattern: store indices in a map, then perform constant‑time lookups while scanning the second list. A brute force or incremental scan shows baseline reasoning, but the hash table solution proves you can reduce time complexity from quadratic to linear.
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.
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.
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.
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.
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.
Python
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.
We use a hash table d to record the strings in list2 and their indices, and a variable mi to record the minimum index sum.
Then, we traverse list1. For each string s, if s appears in list2, we calculate the index i of s in list1 and the index j in list2. If i + j < mi, we update the answer array ans to s and update mi to i + j. If i + j = mi, we add s to the answer array ans.
After traversing, return the answer array ans.
| Approach | Complexity |
|---|---|
| Hash Map Approach | 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. |
| Two Pointer Approach | 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. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Approach | O(n + m) | O(n) | Best general solution. Fast lookups using a hash table. |
| Two Pointer / Incremental Index Scan | O(n^2) worst case | O(1) | Useful when minimizing extra memory or when input lists are very small. |
Minimum Index Sum of Two Lists | JAVA | LeetCode • Knowledge Amplifier • 2,945 views views
Watch 9 more video solutions →Practice Minimum Index Sum of Two Lists with our built-in code editor and test cases.
Practice on FleetCode