Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Intersection Detection subpattern.

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).

Example 3: Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Burger King","Tapioca Express","Shogun"] Output: ["KFC","Burger King","Tapioca Express","Shogun"]

Example 4: Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KNN","KFC","Burger King","Tapioca Express","Shogun"] Output: ["KFC","Burger King","Tapioca Express","Shogun"]

Example 5: Input: list1 = ["KFC"], list2 = ["KFC"] Output: ["KFC"]

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.

Topics and companies

Topics: Hash Table.

Reported in interviews at Oracle, Yelp.

How to practise Minimum Index Sum of Two Lists on Thita.ai

Starter code is provided in C, C#, C++, dart, elixir, erlang, Go, Java, JavaScript, Kotlin, PHP, Python, python3, racket, Ruby, Rust, Scala, Swift and TypeScript. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((m + n) time and O(m * l) space.

Open Minimum Index Sum of Two Lists in the code editor, or read the Minimum Index Sum of Two Lists editorial for a worked solution with its approach and complexity analysis.

Where Minimum Index Sum of Two Lists sits in the DSA pattern sheet

Problems related to Minimum Index Sum of Two Lists

Other problems that use the same Intersection Detection and Linked List Manipulation Patterns techniques:

Preparing this workspace.