Minimum Index Sum of Two Lists

easy hash map string

Problem

Return the common strings between two lists with the smallest index sum (ties allowed).

Inputl1=['S','T','K','H'] l2=['KFC','S','B']

Output['S']

S is at index 0 in l1 and 1 in l2, sum 1.

input

def find_restaurant(l1, l2):
    idx = {s: i for i, s in enumerate(l1)}
    best, out = 10**9, []
    for j, s in enumerate(l2):
        if s in idx:
            t = idx[s] + j
            if t < best: best, out = t, [s]
            elif t == best: out.append(s)
    return out

function findRestaurant(l1, l2) {
  const idx = new Map(l1.map((s, i) => [s, i]));
  let best = Infinity, out = [];
  l2.forEach((s, j) => {
    if (idx.has(s)) {
      const t = idx.get(s) + j;
      if (t < best) { best = t; out = [s]; }
      else if (t === best) out.push(s);
    }
  });
  return out;
}

String[] findRestaurant(String[] l1, String[] l2) {
    Map idx = new HashMap<>();
    for (int i = 0; i < l1.length; i++) idx.put(l1[i], i);
    int best = Integer.MAX_VALUE; List out = new ArrayList<>();
    for (int j = 0; j < l2.length; j++) if (idx.containsKey(l2[j])) {
        int t = idx.get(l2[j]) + j;
        if (t < best) { best = t; out.clear(); out.add(l2[j]); }
        else if (t == best) out.add(l2[j]);
    }
    return out.toArray(new String[0]);
}

vector findRestaurant(vector& l1, vector& l2) {
    unordered_map idx;
    for (int i = 0; i < (int)l1.size(); i++) idx[l1[i]] = i;
    int best = INT_MAX; vector out;
    for (int j = 0; j < (int)l2.size(); j++) if (idx.count(l2[j])) {
        int t = idx[l2[j]] + j;
        if (t < best) { best = t; out = {l2[j]}; }
        else if (t == best) out.push_back(l2[j]);
    }
    return out;
}

Explanation

We want the strings common to both lists whose combined index (position in list1 plus position in list2) is smallest. The fast way is to remember where every list1 string lives, then scan list2 once.

We build a map idx from each string in list1 to its index i. Then we walk list2 with index j; whenever a string also exists in list1, its index sum is t = idx[s] + j.

We track the best (smallest) sum seen. If t beats the current best, we restart the answer list with just this string. If t ties the best, we append it, since the problem allows multiple winners.

Example: l1 = ['S','T','K','H'], l2 = ['KFC','S','B']. Scanning list2, 'KFC' and 'B' aren't in list1, but 'S' is at index 0 in l1 and 1 in l2, giving sum 1. That's the only match, so the answer is ['S'].

Because the map gives constant-time lookups, the whole thing is one pass over each list, O(n + m).

Time: O(n+m) Space: O(n)