Table of Contents

# Minimum Index Sum of Two Lists – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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 <= 1000`

`1 <= list1[i].length, list2[i].length <= 30`

`list1[i]`

and`list2[i]`

consist of spaces`' '`

and English letters.- All the strings of
`list1`

are**unique**. - All the strings of
`list2`

are**unique**.

# C++ Minimum Index Sum of Two Lists LeetCode Solution

```
``````
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string>res;
unordered_map<string,int>m;
int min = INT_MAX;
for(int i = 0; i < list1.size(); i++) m[list1[i]] = i;
for(int i = 0; i < list2.size(); i++)
if(m.count(list2[i]) != 0)
if(m[list2[i]] + i < min) min = m[list2[i]] + i, res.clear(), res.push_back(list2[i]);
else if(m[list2[i]] + i == min) res.push_back(list2[i]);
return res;
}
```

# Java Minimum Index Sum of Two Lists LeetCode Solution

```
``````
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String, Integer> map = new HashMap<>();
List<String> res = new LinkedList<>();
int minSum = Integer.MAX_VALUE;
for (int i=0;i<list1.length;i++) map.put(list1[i], i);
for (int i=0;i<list2.length;i++) {
Integer j = map.get(list2[i]);
if (j != null && i + j <= minSum) {
if (i + j < minSum) { res.clear(); minSum = i+j; }
res.add(list2[i]);
}
}
return res.toArray(new String[res.size()]);
}
```

# Python 3 Minimum Index Sum of Two Lists LeetCode Solution

```
``````
def findRestaurant(self, A, B):
Aindex = {u: i for i, u in enumerate(A)}
best, ans = 1e9, []
for j, v in enumerate(B):
i = Aindex.get(v, 1e9)
if i + j < best:
best = i + j
ans = [v]
elif i + j == best:
ans.append(v)
return ans
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1