Skip to main content

Minimum Index Sum of Two Lists

Problem statement​

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

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 restaurant they both like is "Shogun".

Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]Output: ["Shogun"]Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

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 stings of list1 are unique.
  • All the stings of list2 are unique.

My solution​

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function(list1, list2) {
    const map = new Map();
    
    for (let idx = 0; idx < list1.length; idx++) {
        const item = list1[idx]
        if (!map.has(item)) {
            map.set(item, [false, -1])
        }
        
        map.set(item, [false, idx])
    }
    
    // console.log(map)
    let minIndex = Number.MAX_SAFE_INTEGER
    
    for (let idx = 0; idx < list2.length; idx++) {
        const item = list2[idx]
        if (map.has(item)) {
            const [_, oldIdx] = map.get(item)
            const sumIdx = oldIdx + idx
            minIndex = Math.min(minIndex, sumIdx)
            map.set(item, [true, sumIdx])
        }
    }
    
    // const result = [];
    return [...map].filter(([key, [found, idxSum]]) => found && idxSum === minIndex).map(([key]) => key)
//     for (const [key, [found, idxSum]] of map.entries()) {
//         if (found && idxSum === minIndex) {
//             // if ()
//             result.push(key)
//         }
//     }
    
//     // console.log(result)

    // return result
};