Code Logo

Minimum Index Sum of Two Lists

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given two arrays of strings representing restaurant preferences for two people, find the common restaurants that appear in both lists and have the smallest index sum. An index sum is the sum of the string's position in list1 plus its position in list2 (0-indexed). If there is a tie for the smallest index sum, return all tied restaurants in any order.

A brute force double loop would compare every pair of entries in O(n * m) time. A hash map approach reduces this to O(n + m): first build a hash map from list1 storing each restaurant's index. Then iterate list2, and for each restaurant that appears in the hash map, compute the index sum. Track the minimum sum seen so far. If a restaurant's sum equals the current minimum, add it to the result. If it's less, start a new result list with just this restaurant.

This is a classic hash map look-up pattern. The map from list1 provides O(1) index lookups, making the overall algorithm linear. It also naturally handles the tie case by collecting restaurants with the same minimum sum.

Edge cases include lists with no common restaurant (return empty array), both lists identical (return all in order of list1 with sum = i + i), and single-element lists that match (return that element).

Example Input & Output

Example 1
Input
["x"], ["x"]
Output
["x"]
Explanation

Single common element at sum 0+0=0.

Example 2
Input
["a","b"], ["c","d"]
Output
[]
Explanation

No common restaurants.

Example 3
Input
["happy","sad","good"], ["sad","happy","good"]
Output
["sad","happy"]
Explanation

Both have sum 1+0=1 and 0+1=1.

Example 4
Input
["Shogun","Tapioca Express","Burger King","KFC"], ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output
["Shogun"]
Explanation

Shogun is the only common restaurant at sum 0+3=3.

Example 5
Input
["Shogun","Tapioca Express","Burger King","KFC"], ["KFC","Shogun","Burger King"]
Output
["Shogun"]
Explanation

Shogun sum=0+1=1, KFC sum=3+0=3, Burger King sum=2+2=4.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Index Sum of Two Lists
Recommendation Algorithm Flow for Minimum Index Sum of Two Lists

Solution Approach

Build index map from list1. Iterate list2, check if restaurant is in map, compute sum, track minimum.

function solution(list1, list2) {
  var idxMap = {};
  for (var i = 0; i < list1.length; i++) idxMap[list1[i]] = i;
  var best = 999999;
  var result = [];
  for (var j = 0; j < list2.length; j++) {
    var w = list2[j];
    if (idxMap[w] !== undefined) {
      var sum = idxMap[w] + j;
      if (sum < best) { best = sum; result = [w]; }
      else if (sum === best) result.push(w);
    }
  }
  return result;
}

Time O(n+m), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public String[] solution(String[] list1, String[] list2) {
        Map<String,Integer> idx = new HashMap<>();
        for (int i = 0; i < list1.length; i++) idx.put(list1[i], i);
        int best = Integer.MAX_VALUE;
        List<String> res = new ArrayList<>();
        for (int j = 0; j < list2.length; j++) {
            String w = list2[j];
            if (idx.containsKey(w)) {
                int sum = idx.get(w) + j;
                if (sum < best) { best = sum; res.clear(); res.add(w); }
                else if (sum == best) res.add(w);
            }
        }
        return res.toArray(new String[0]);
    }
}