Skip to main content
Talentd

Minimum Index Sum of Two Lists - Solution & Explanation

EasyArrayHash TableString15 min readAsked at: Amazon, Google, Bloomberg +1
Practice this problem

Problem Statement

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.
  • There is at least a common string between list1 and list2.

Approach Overview

Problem Overview: You get two string arrays representing favorite restaurants from two people. The task is to return the restaurant(s) that appear in both lists with the smallest possible index sum i + j. If multiple restaurants share the same minimum sum, return all of them.

Approach 1: Hash Map Approach (O(n + m) time, O(n) space)

This is the standard solution using a hash table. First iterate through list1 and store each restaurant with its index in a hash map. Then iterate through list2. For every restaurant, check if it exists in the map using an O(1) lookup. If it exists, compute the index sum i + j. Track the smallest sum seen so far and update the result list accordingly. If a new smaller sum appears, clear the result and add the new restaurant; if the sum ties with the minimum, append it.

The key insight is constant‑time membership checking. Instead of comparing every pair of restaurants, you reduce the search to direct hash lookups. This turns a potential O(n*m) comparison into a linear scan. The approach works well for typical array intersection problems where fast membership checks are required.

Approach 2: Two Pointer / Incremental Index Scan (O(n^2) worst case, O(1) extra space)

This approach avoids extra data structures and instead scans both lists using increasing index sums. Start with sum = 0 and check all index pairs where i + j = sum. For each pair, compare the restaurant names directly. As soon as you find matches, record them. Once matches appear for a particular sum, you can stop because any later sums will be larger.

The technique behaves like a diagonal traversal over the conceptual matrix of index pairs. It is simple and uses constant extra space, relying only on string comparisons between the two lists. However, because comparisons may still grow quadratically in the worst case, it is less efficient for large inputs. Still, for short lists or environments where extra memory is restricted, it can be acceptable.

Since restaurant names are strings, equality checks are direct string comparisons. The main optimization comes from minimizing unnecessary comparisons or lookups.

Recommended for interviews: The hash map approach is what interviewers expect. It demonstrates recognition of a classic pattern: store indices in a map, then perform constant‑time lookups while scanning the second list. A brute force or incremental scan shows baseline reasoning, but the hash table solution proves you can reduce time complexity from quadratic to linear.

Approach 1: Hash Map Approach

This approach uses a hash map to store the indices of the elements from the first list. By iterating through the second list, we can check for common strings and calculate the minimum index sum efficiently.

This solution iterates through the first list and stores each string with its index in hashmap and index_map. It then iterates through the second list, checking if each element is in the hashmap. It computes the index sum and records the result if it is the minimum found so far.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m) where n is the size of list1 and m is the size of list2. Space Complexity: O(n) for hash map storage.

Try this approach in the editor →

Approach 2: Two Pointer Approach

This approach uses two pointers to traverse both lists simultaneously. This can be useful in certain scenarios where both lists are already sorted in some order.

In this Python solution, we first sort both lists by their string values while storing their original indexes. Then we simultaneously traverse both sorted lists using two pointers to find common elements, calculate their index sums, and determine the minimum sums.

Code

Python

Python

Complexity

Time Complexity: O(n log n + m log m) due to sorting, where n is the size of list1 and m is the size of list2. Space Complexity: O(n + m) for storing sorted lists.

Try this approach in the editor →

Approach 3: Hash Table

We use a hash table d to record the strings in list2 and their indices, and a variable mi to record the minimum index sum.

Then, we traverse list1. For each string s, if s appears in list2, we calculate the index i of s in list1 and the index j in list2. If i + j < mi, we update the answer array ans to s and update mi to i + j. If i + j = mi, we add s to the answer array ans.

After traversing, return the answer array ans.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Hash Map Approach

Time Complexity: O(n * m) where n is the size of list1 and m is the size of list2. Space Complexity: O(n) for hash map storage.

Two Pointer Approach

Time Complexity: O(n log n + m log m) due to sorting, where n is the size of list1 and m is the size of list2. Space Complexity: O(n + m) for storing sorted lists.

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map ApproachO(n + m)O(n)Best general solution. Fast lookups using a hash table.
Two Pointer / Incremental Index ScanO(n^2) worst caseO(1)Useful when minimizing extra memory or when input lists are very small.

Video Solution

Minimum Index Sum of Two Lists | JAVA | LeetCode • Knowledge Amplifier • 2,975 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Index Sum of Two Lists easy or hard?
Minimum Index Sum of Two Lists is classified as an Easy problem. The challenge mainly involves recognizing that a hash map eliminates nested comparisons and reduces the time complexity from O(n*m) to O(n + m).
Minimum Index Sum of Two Lists Python/Java solution
Both Python and Java implementations follow the same idea: build a hash map from the first list, iterate through the second list, compute index sums, and track the minimum. Python typically uses a dictionary, while Java uses a HashMap.
How to solve Minimum Index Sum of Two Lists in O(n)?
Store each restaurant from the first list in a hash map with its index. Then iterate through the second list and check if the restaurant exists in the map. For every match, compute the index sum and maintain the minimum. This reduces the problem to linear time with constant‑time hash lookups.
What is the best approach for Minimum Index Sum of Two Lists?
The best approach uses a hash map to store restaurant indices from the first list, then scans the second list to compute index sums. Each lookup runs in O(1), so the overall complexity becomes O(n + m). This is the standard optimal solution expected in coding interviews.
Is Minimum Index Sum of Two Lists asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving hash tables and array scanning. Variants of it appear in interviews at companies like Amazon and Google because it tests efficient lookups, handling ties, and understanding time complexity tradeoffs.
What data structure is used in Minimum Index Sum of Two Lists?
A hash table (hash map) is the primary data structure used in the optimal solution. It stores restaurant names as keys and their indices as values, allowing O(1) lookups when scanning the second list.
What is the time complexity of Minimum Index Sum of Two Lists?
The optimal hash map solution runs in O(n + m) time, where n and m are the lengths of the two lists. Building the map takes O(n), and scanning the second list with constant‑time lookups takes O(m). Space complexity is O(n) for storing indices.

Ready to solve this problem?

Practice Minimum Index Sum of Two Lists with our built-in code editor and test cases.

Practice on FleetCode
Previous

Intersection of Two Linked Lists