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 thecommon strings with the least index sum. Return the answer in any order.

Examples

Example 1

1
2
3

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

1
2
3

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

1
2
3
4
5
6
7

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.
  • There is at least a common string between list1 and list2.

Solution

Method 1 – Hash Map Index Tracking

Intuition

To find common strings with the least index sum, we can store the indices of strings from the first list in a hash map, then scan the second list and check for common strings, keeping track of the minimum index sum.

Approach

  1. Store each string from list1 with its index in a hash map.
  2. Iterate through list2, and for each string, if it exists in the hash map, calculate the index sum.
  3. Track the minimum index sum and collect all strings with that sum.
  4. Return the list of common strings with the minimum index sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> idx;
        for (int i = 0; i < list1.size(); ++i) idx[list1[i]] = i;
        int mn = INT_MAX;
        vector<string> ans;
        for (int j = 0; j < list2.size(); ++j) {
            if (idx.count(list2[j])) {
                int s = idx[list2[j]] + j;
                if (s < mn) {
                    mn = s;
                    ans.clear();
                    ans.push_back(list2[j]);
                } else if (s == mn) {
                    ans.push_back(list2[j]);
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func findRestaurant(list1 []string, list2 []string) []string {
    idx := make(map[string]int)
    for i, s := range list1 {
        idx[s] = i
    }
    mn := 1 << 30
    var ans []string
    for j, s := range list2 {
        if i, ok := idx[s]; ok {
            sum := i + j
            if sum < mn {
                mn = sum
                ans = []string{s}
            } else if sum == mn {
                ans = append(ans, s)
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> idx = new HashMap<>();
        for (int i = 0; i < list1.length; i++) idx.put(list1[i], i);
        int mn = Integer.MAX_VALUE;
        List<String> ans = new ArrayList<>();
        for (int j = 0; j < list2.length; j++) {
            if (idx.containsKey(list2[j])) {
                int s = idx.get(list2[j]) + j;
                if (s < mn) {
                    mn = s;
                    ans.clear();
                    ans.add(list2[j]);
                } else if (s == mn) {
                    ans.add(list2[j]);
                }
            }
        }
        return ans.toArray(new String[0]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun findRestaurant(list1: Array<String>, list2: Array<String>): Array<String> {
        val idx = list1.withIndex().associate { it.value to it.index }
        var mn = Int.MAX_VALUE
        val ans = mutableListOf<String>()
        for ((j, s) in list2.withIndex()) {
            val i = idx[s]
            if (i != null) {
                val sum = i + j
                if (sum < mn) {
                    mn = sum
                    ans.clear()
                    ans.add(s)
                } else if (sum == mn) {
                    ans.add(s)
                }
            }
        }
        return ans.toTypedArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def find_restaurant(list1: list[str], list2: list[str]) -> list[str]:
    idx = {s: i for i, s in enumerate(list1)}
    mn = float('inf')
    ans = []
    for j, s in enumerate(list2):
        if s in idx:
            sidx = idx[s] + j
            if sidx < mn:
                mn = sidx
                ans = [s]
            elif sidx == mn:
                ans.append(s)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
        use std::collections::HashMap;
        let mut idx = HashMap::new();
        for (i, s) in list1.iter().enumerate() {
            idx.insert(s, i);
        }
        let mut mn = usize::MAX;
        let mut ans = vec![];
        for (j, s) in list2.iter().enumerate() {
            if let Some(&i) = idx.get(s) {
                let sum = i + j;
                if sum < mn {
                    mn = sum;
                    ans.clear();
                    ans.push(s.clone());
                } else if sum == mn {
                    ans.push(s.clone());
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    findRestaurant(list1: string[], list2: string[]): string[] {
        const idx = new Map<string, number>();
        list1.forEach((s, i) => idx.set(s, i));
        let mn = Number.MAX_SAFE_INTEGER;
        let ans: string[] = [];
        list2.forEach((s, j) => {
            if (idx.has(s)) {
                const sum = idx.get(s)! + j;
                if (sum < mn) {
                    mn = sum;
                    ans = [s];
                } else if (sum === mn) {
                    ans.push(s);
                }
            }
        });
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + m), where n and m are the lengths of list1 and list2. Each list is scanned once.
  • 🧺 Space complexity: O(n), for the hash map storing indices.