JavaScript O(n+m) solution with explaination


  • 0

    Step1: Generate a index map of list1
    Step2: Traverse list2, check if the restaurant exists in list1 or not by accessing the corresponding field in map
    Step3: Sum the index of the above restaurant and keep the minimum
    Step4: Retrieve all the restaurants with minimum sum of index

    /**
     * @param {string[]} list1
     * @param {string[]} list2
     * @return {string[]}
     */
    var findRestaurant = function(list1, list2) {
        let map1 = {};
        let map2 = {};
        let minIdx = 2000;
        let restaurant = [];
        
        // Create list1 index map
        list1.forEach((item, idx) => {
            map1[item] = idx;
        });
    
        list2.forEach((item, idx) => {
            // If this restaurant also exists in list1
            if (map1[item] !==undefined) {
                // Keep the sum of index
                map2[item] = map1[item] + idx;
                if (map2[item] < minIdx) {
                    // Always remember the minimum sum of index
                    minIdx =  map2[item];
                }
            }
        });
        
        Object.keys(map2).forEach(key => {
           // Retrive all the restaurant with minimum sum of index
           if (map2[key] <= minIdx) {
               restaurant.push(key);
           }
        });
        
        return restaurant;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.