599. Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists (LeetCode 599) 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.

How to solve Minimum Index Sum of Two Lists

Minimum Index Sum of Two Lists is a Detect Linked List Intersection problem, part of Linked List Manipulation Patterns. Learn to find the intersection point of two linked lists using the two-pointer technique.

Work towards the solution in these steps:

1. Think about how to quickly check if an element from one list exists in the other; what data structure can help achieve constant time lookups?
2. Try mapping each restaurant in the first list to its index to facilitate quick index retrieval when scanning the second list.
3. As you iterate through the second list, calculate the sum of the indices for common restaurants and keep track of the minimum sum encountered.

The reference solution runs in O((m + n)) time and O(m * l) space.

The Minimum Index Sum of Two Lists solution and editorial walks through the full approach with reference code.

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

• Linked List Manipulation Patterns pattern guide
• Intersection Detection subpattern
• The full DSA patterns sheet

Problems related to Minimum Index Sum of Two Lists

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

• Intersection of Two Linked Lists — Easy, same subpattern
• Add Two Numbers — Medium, same pattern
• Insert Greatest Common Divisors in Linked List — Medium, same pattern
• Merge Two Sorted Lists — Easy, same pattern
• Odd Even Linked List — Medium, same pattern
• Palindrome Linked List — Easy, same pattern

Minimum Index Sum of Two Lists FAQ