599. Minimum Index Sum of Two Lists

599. Minimum Index Sum of Two Lists

Problem Description 

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

 

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 common string is "Shogun".

Example 2:

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:

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.

Approach: HashMap (Linear)

• We make use of a HashMap to solve the given problem in a different way in this approach.
• Firstly, we traverse over the whole list1 and create an entry for each element of list1 in a HashMap map, of the form (list[i], I).
• Here, i refers to the index of i​th element, and list[i] is the ith element itself.
• Thus, we create a mapping from the elements of the list1 to their indices.
• Now, we traverse over list2.
• For every element, list2[i], of list2 encountered, we check if the same element already exists as a key in the map.
• If so, it means that the element exists in both list1 and list2.
• Thus, we find out the sum of indices corresponding to this element in the two lists,
• given by sum = map.get(list[i]) + I.
• If this sum is lesser than the minimum sum obtained till now, we update the result list to be returned, output,
• with the element list2[i] as the only entry in it.
• If the sum is equal to the minimum sum obtained till now, we put an extra entry corresponding to the element list2[i] in the output list.

 

Let`s Code IT!

/**
 * @param {string[]} list1
 * @param {string[]} list2
 * @return {string[]}
 */
var findRestaurant = function(list1, list2) {
    let map = {};
    for(let i=0;i<list1.length;i++){
        map[list1[i]] = i;
    }
    let output = [];
    let leastIndexSum = 9999;
    for(let i=0;i<list2.length;i++){
        if(map[list2[i]] != undefined){
            if(leastIndexSum > i+map[list2[i]]){
                output = [list2[i]];
                leastIndexSum= i+map[list2[i]];
            }else if(leastIndexSum == i+map[list2[i]]){
                output.push(list2[i])
            }
        }
    }
    return output;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #599. Minimum Index Sum of Two Lists
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!