DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

1

Minimum Index Sum of Two Lists

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.

SOLUTION:

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        l1pos = {}
        l2pos = {}
        for i, num in enumerate(list1):
            l1pos[num] = i
        for i, num in enumerate(list2):
            l2pos[num] = i
        common = set.intersection(set(list1), set(list2))
        sums = {}
        for c in common:
            curr = l1pos[c] + l2pos[c]
            sums[curr] = sums.get(curr, []) + [c]
        return sums[min(sums.keys())]
Enter fullscreen mode Exit fullscreen mode

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more