Solution 1 - Index Map

Map list1 items to indices; scan list2 and keep items with minimal index sum.

TimeComplexity: O(m+n)

SpaceComplexity: O(m)

""" 0599.1 - Minimum Index Sum of Two Lists - Solution 1 - Index Map """

class Solution:
    def findRestaurant(self, list1, list2):
        pos = {x: i for i, x in enumerate(list1)}
        best = 10**9
        out = []

        for j, x in enumerate(list2):
            if x in pos:
                s = pos[x] + j
                if s < best:
                    best = s
                    out = [x]
                elif s == best:
                    out.append(x)

        return out

if __name__ == "__main__":
    print(Solution().findRestaurant(["Shogun","KFC"], ["KFC","Shogun"]))

function findRestaurant(list1,list2){
 const pos=new Map(list1.map((x,i)=>[x,i]));
 let best=Infinity, out=[];
 for(let j=0;j<list2.length;j++){
  const x=list2[j];
  if(pos.has(x)){
   const s=pos.get(x)+j;
   if(s<best){best=s;out=[x];}
   else if(s===best) out.push(x);
  }
 }
 return out;
}

function findRestaurant(list1:string[], list2:string[]):string[]{
 const pos:Map<string,number>=new Map(list1.map((x,i)=>[x,i]));
 let best=Infinity;
 let out:string[]=[];
 for(let j=0;j<list2.length;j++){
  const x=list2[j];
  const i=pos.get(x);
  if(i!==undefined){
   const s=i+j;
   if(s<best){best=s;out=[x];}
   else if(s===best) out.push(x);
  }
 }
 return out;
}

package main

func findRestaurant(list1 []string, list2 []string) []string {
	pos := map[string]int{}
	for i, x := range list1 {
		pos[x] = i
	}

	best := int(^uint(0) >> 1)
	out := []string{}

	for j, x := range list2 {
		if i, ok := pos[x]; ok {
			s := i + j
			if s < best {
				best = s
				out = []string{x}
			} else if s == best {
				out = append(out, x)
			}
		}
	}
	return out
}

func main() {}

use std::collections::HashMap;

fn find_restaurant(list1: &[&str], list2: &[&str]) -> Vec<String> {
	let pos: HashMap<&str, usize> = list1.iter().enumerate().map(|(i, &x)| (x, i)).collect();
	let mut best = usize::MAX;
	let mut out: Vec<String> = vec![];

	for (j, &x) in list2.iter().enumerate() {
		if let Some(&i) = pos.get(x) {
			let s = i + j;
			if s < best {
				best = s;
				out = vec![x.to_string()];
			} else if s == best {
				out.push(x.to_string());
			}
		}
	}
	out
}

fn main() {}

0599 - Minimum Index Sum of Two Lists

Solution 1 - Index Map