Minimum Index Sum of Two Lists solution and explanation
Google
9 more videos on this problem
Minimum Index Sum of Two Lists | JAVA | LeetCodeKnowledge Amplifier · 10:58 · 2K views
LeetCode 599 Minimum Index Sum of Two Lists - Interview Question Solved Using HashMapAlgorithmicIQ · 16:35 · 2K views
599. Minimum Index Sum of Two Lists | #9 | Hash Table Playlist #hashtable #leetcode #algorithmsCTO Bhaiya · 15:27 · 2K views
599. Minimum Index Sum of Two Lists | Leetcode | PythonAbdullah Arshed · 3:31 · 1K views
599. Minimum Index Sum of Two ListsJake LeetCode · 4:12 · 1K views
Easy - leetcode 599 - Minimum Index Sum of Two Lists (Best View in 1080)algoupgrade · 11:36 · 1K views
599. Minimum Index Sum of Two Lists || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 2:16 · 1K views
Leetcode solving: 599 Minimum Index Sum of Two ListsMath Geeks · 4:05 · 991 views
LeetCode 599 : Minimum Index Sum of Two Lists || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 17:16 · 711 views
LeetCode 599 | Minimum Index Sum of Two Lists | HashMap | Debug | JavaSleepy Cracker · 8:44 · 633 views
The problem
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]andlist2[i]consist of spaces' 'and English letters.- All the strings of
list1are unique. - All the strings of
list2are unique. - There is at least a common string between
list1andlist2.
Approach overview
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.
Approach 1: Hash Map Approach
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.
def findIndexSum(list1, list2):
index_map = {s: i for i, s in enumerate(list1)}
min_sum = float('inf')
result = []
for j, s in enumerate(list2):
if s in index_map:
i = index_map[s]
sum_index = i + j
if sum_index < min_sum:
min_sum = sum_index
result = [s]
elif sum_index == min_sum:
result.append(s)
return result
list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]
list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
print(findIndexSum(list1, list2))import java.util.*;
public class Solution {
public String[] findIndexSum(String[] list1, String[] list2) {
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
List<String> result = new ArrayList<>();
int minSum = Integer.MAX_VALUE;
for (int j = 0; j < list2.length; j++) {
if (map.containsKey(list2[j])) {
int sum = j + map.get(list2[j]);
if (sum < minSum) {
result.clear();
result.add(list2[j]);
minSum = sum;
} else if (sum == minSum) {
result.add(list2[j]);
}
}
}
return result.toArray(new String[result.size()]);
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
String[] result = solution.findIndexSum(list1, list2);
System.out.println(Arrays.toString(result));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<string> findIndexSum(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> indexMap;
for (int i = 0; i < list1.size(); ++i) {
indexMap[list1[i]] = i;
}
vector<string> result;
int minSum = INT_MAX;
for (int j = 0; j < list2.size(); ++j) {
if (indexMap.find(list2[j]) != indexMap.end()) {
int sum = j + indexMap[list2[j]];
if (sum < minSum) {
result.clear();
result.push_back(list2[j]);
minSum = sum;
} else if (sum == minSum) {
result.push_back(list2[j]);
}
}
}
return result;
}
int main() {
vector<string> list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
vector<string> list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
vector<string> result = findIndexSum(list1, list2);
for (const auto& str : result) {
cout << str << endl;
}
return 0;
}function findIndexSum(list1, list2) {
const map = new Map();
list1.forEach((item, index) => map.set(item, index));
let minSum = Infinity;
const result = [];
list2.forEach((item, index) => {
if (map.has(item)) {
const sum = index + map.get(item);
if (sum < minSum) {
result.length = 0;
result.push(item);
minSum = sum;
} else if (sum === minSum) {
result.push(item);
}
}
});
return result;
}
const list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"];
const list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"];
console.log(findIndexSum(list1, list2));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_LENGTH 30
#define MAX_SIZE 1000
int* findIndexSum(char* list1[], int size1, char* list2[], int size2, int* returnSize) {
char* hashmap[MAX_SIZE];
int index_map[MAX_SIZE];
int min_sum = 2000; // Initialize with a large number
for (int i = 0; i < size1; ++i) {
hashmap[i] = list1[i];
index_map[i] = i;
}
char** result = malloc(size2 * sizeof(char*));
int resultIndex = 0;
for (int j = 0; j < size2; ++j) {
for (int k = 0; k < size1; ++k) {
if (strcmp(list2[j], hashmap[k]) == 0) {
int sum = j + index_map[k];
if (sum < min_sum) {
resultIndex = 0;
result[resultIndex++] = hashmap[k];
min_sum = sum;
} else if (sum == min_sum) {
result[resultIndex++] = hashmap[k];
}
break;
}
}
}
*returnSize = resultIndex;
return result;
}
int main() {
int returnSize = 0;
char* list1[] = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
char* list2[] = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
int size1 = sizeof(list1) / sizeof(list1[0]);
int size2 = sizeof(list2) / sizeof(list2[0]);
char** result = findIndexSum(list1, size1, list2, size2, &returnSize);
for (int i = 0; i < returnSize; ++i) {
printf("%s\n", result[i]);
}
free(result);
}using System;
using System.Collections.Generic;
public class Solution {
public string[] FindIndexSum(string[] list1, string[] list2) {
Dictionary<string, int> map = new Dictionary<string, int>();
for (int i = 0; i < list1.Length; i++) {
map[list1[i]] = i;
}
List<string> result = new List<string>();
int minSum = int.MaxValue;
for (int j = 0; j < list2.Length; j++) {
if (map.ContainsKey(list2[j])) {
int sum = j + map[list2[j]];
if (sum < minSum) {
result.Clear();
result.Add(list2[j]);
minSum = sum;
} else if (sum == minSum) {
result.Add(list2[j]);
}
}
}
return result.ToArray();
}
public static void Main() {
Solution solution = new Solution();
string[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
string[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
string[] result = solution.FindIndexSum(list1, list2);
Console.WriteLine(string.Join(", ", result));
}
}In this Python solution, we use a dictionary to store indices from list1. Then, we iterate over list2, checking for common elements and calculating the index sum, thereby determining the list with 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.
Approach 2: Two Pointer Approach
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.
def findIndexSumTwoPointer(list1, list2):
i = j = 0
min_sum = float('inf')
result = []
list1_sorted = sorted((s, i) for i, s in enumerate(list1))
list2_sorted = sorted((s, i) for i, s in enumerate(list2))
while i < len(list1_sorted) and j < len(list2_sorted):
if list1_sorted[i][0] == list2_sorted[j][0]:
sum_index = list1_sorted[i][1] + list2_sorted[j][1]
if sum_index < min_sum:
min_sum = sum_index
result = [list1_sorted[i][0]]
elif sum_index == min_sum:
result.append(list1_sorted[i][0])
i += 1
j += 1
elif list1_sorted[i][0] < list2_sorted[j][0]:
i += 1
else:
j += 1
return result
list1 = ['happy', 'sad', 'good']
list2 = ['sad', 'happy', 'good']
print(findIndexSumTwoPointer(list1, list2))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.
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.
Approach 3: Hash Table
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.
function findRestaurant(list1: string[], list2: string[]): string[] {
const d = new Map<string, number>(list2.map((s, i) => [s, i]));
let mi = Infinity;
const ans: string[] = [];
list1.forEach((s, i) => {
if (d.has(s)) {
const j = d.get(s)!;
if (i + j < mi) {
mi = i + j;
ans.length = 0;
ans.push(s);
} else if (i + j === mi) {
ans.push(s);
}
}
});
return ans;
}func findRestaurant(list1 []string, list2 []string) []string {
d := map[string]int{}
for i, s := range list2 {
d[s] = i
}
ans := []string{}
mi := 1 << 30
for i, s := range list1 {
if j, ok := d[s]; ok {
if i+j < mi {
mi = i + j
ans = []string{s}
} else if i+j == mi {
ans = append(ans, s)
}
}
}
return ans
}use std::collections::HashMap;
impl Solution {
pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
let mut d = HashMap::new();
for (i, s) in list2.iter().enumerate() {
d.insert(s, i);
}
let mut ans = Vec::new();
let mut mi = std::i32::MAX;
for (i, s) in list1.iter().enumerate() {
if let Some(&j) = d.get(s) {
if (i as i32 + j as i32) < mi {
mi = i as i32 + j as i32;
ans = vec![s.clone()];
} else if (i as i32 + j as i32) == mi {
ans.push(s.clone());
}
}
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Minimum Index Sum of Two Lists easy or hard?
Minimum Index Sum of Two Lists is classified as an Easy problem. The challenge mainly involves recognizing that a hash map eliminates nested comparisons and reduces the time complexity from O(n*m) to O(n + m).
Minimum Index Sum of Two Lists Python/Java solution
Both Python and Java implementations follow the same idea: build a hash map from the first list, iterate through the second list, compute index sums, and track the minimum. Python typically uses a dictionary, while Java uses a HashMap.
How to solve Minimum Index Sum of Two Lists in O(n)?
Store each restaurant from the first list in a hash map with its index. Then iterate through the second list and check if the restaurant exists in the map. For every match, compute the index sum and maintain the minimum. This reduces the problem to linear time with constant‑time hash lookups.
What is the best approach for Minimum Index Sum of Two Lists?
The best approach uses a hash map to store restaurant indices from the first list, then scans the second list to compute index sums. Each lookup runs in O(1), so the overall complexity becomes O(n + m). This is the standard optimal solution expected in coding interviews.
Is Minimum Index Sum of Two Lists asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hash tables and array scanning. Variants of it appear in interviews at companies like Amazon and Google because it tests efficient lookups, handling ties, and understanding time complexity tradeoffs.
What data structure is used in Minimum Index Sum of Two Lists?
A hash table (hash map) is the primary data structure used in the optimal solution. It stores restaurant names as keys and their indices as values, allowing O(1) lookups when scanning the second list.
What is the time complexity of Minimum Index Sum of Two Lists?
The optimal hash map solution runs in O(n + m) time, where n and m are the lengths of the two lists. Building the map takes O(n), and scanning the second list with constant‑time lookups takes O(m). Space complexity is O(n) for storing indices.