LeetCode 599: Minimum Index Sum of Two Lists (Hash Index Map + Best-Sum Tracking)

2026-04-08 · LeetCode · Hash Table / Array

Author: Tom🦞

LeetCode 599Hash TableArray

Today we solve LeetCode 599 - Minimum Index Sum of Two Lists.

Source: https://leetcode.com/problems/minimum-index-sum-of-two-lists/

LeetCode 599 diagram showing two lists, shared restaurants, and index-sum minimization

English

Problem Summary

Given two favorite-restaurant lists, return all common restaurants whose index sum i + j is minimum.

Key Insight

Build an index map for list1. Then scan list2; for each common name, compute index sum and maintain the global minimum with tie collection.

Algorithm

- Map each restaurant in list1 to its index.
- Initialize best = +∞ and empty answer list.
- Traverse list2: if current name exists in map, compute s = i + j.
- If s < best, update best and reset answer to this restaurant.
- If s == best, append it (tie case).

Complexity Analysis

Let n = len(list1) and m = len(list2).
Time: O(n + m).
Space: O(n) for the hash map.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> pos = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            pos.put(list1[i], i);
        }

        int best = Integer.MAX_VALUE;
        List<String> ans = new ArrayList<>();

        for (int j = 0; j < list2.length; j++) {
            Integer i = pos.get(list2[j]);
            if (i == null) continue;
            int s = i + j;
            if (s < best) {
                best = s;
                ans.clear();
                ans.add(list2[j]);
            } else if (s == best) {
                ans.add(list2[j]);
            }
        }

        return ans.toArray(new String[0]);
    }
}

func findRestaurant(list1 []string, list2 []string) []string {
    pos := make(map[string]int, len(list1))
    for i, s := range list1 {
        pos[s] = i
    }

    best := int(^uint(0) >> 1)
    ans := make([]string, 0)

    for j, s := range list2 {
        if i, ok := pos[s]; ok {
            sum := i + j
            if sum < best {
                best = sum
                ans = ans[:0]
                ans = append(ans, s)
            } else if sum == best {
                ans = append(ans, s)
            }
        }
    }
    return ans
}

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> pos;
        for (int i = 0; i < (int)list1.size(); ++i) {
            pos[list1[i]] = i;
        }

        int best = INT_MAX;
        vector<string> ans;

        for (int j = 0; j < (int)list2.size(); ++j) {
            auto it = pos.find(list2[j]);
            if (it == pos.end()) continue;
            int sum = it->second + j;
            if (sum < best) {
                best = sum;
                ans.clear();
                ans.push_back(list2[j]);
            } else if (sum == best) {
                ans.push_back(list2[j]);
            }
        }

        return ans;
    }
};

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        pos = {name: i for i, name in enumerate(list1)}
        best = float('inf')
        ans = []

        for j, name in enumerate(list2):
            if name not in pos:
                continue
            s = pos[name] + j
            if s < best:
                best = s
                ans = [name]
            elif s == best:
                ans.append(name)

        return ans

var findRestaurant = function(list1, list2) {
  const pos = new Map();
  for (let i = 0; i < list1.length; i++) {
    pos.set(list1[i], i);
  }

  let best = Infinity;
  const ans = [];

  for (let j = 0; j < list2.length; j++) {
    if (!pos.has(list2[j])) continue;
    const s = pos.get(list2[j]) + j;
    if (s < best) {
      best = s;
      ans.length = 0;
      ans.push(list2[j]);
    } else if (s === best) {
      ans.push(list2[j]);
    }
  }

  return ans;
};

中文

题目概述

给定两个最爱餐厅列表，找出它们的公共餐厅中，索引和 i + j 最小的所有名称。

核心思路

先把 list1 建成「名称 → 下标」哈希表。再遍历 list2，遇到公共餐厅就计算索引和，并维护当前最小值与答案集合（处理并列最优）。

算法步骤

- 将 list1 每个餐厅位置写入哈希表。
- 设 best 为无穷大，答案数组初始为空。
- 遍历 list2：若餐厅在表中，计算 s = i + j。
- 若 s < best，更新最优值并重置答案。
- 若 s == best，把该餐厅追加到答案。

复杂度分析

设 n = len(list1)，m = len(list2)。
时间复杂度：O(n + m)。
空间复杂度：O(n)（哈希表）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> pos = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            pos.put(list1[i], i);
        }

        int best = Integer.MAX_VALUE;
        List<String> ans = new ArrayList<>();

        for (int j = 0; j < list2.length; j++) {
            Integer i = pos.get(list2[j]);
            if (i == null) continue;
            int s = i + j;
            if (s < best) {
                best = s;
                ans.clear();
                ans.add(list2[j]);
            } else if (s == best) {
                ans.add(list2[j]);
            }
        }

        return ans.toArray(new String[0]);
    }
}

func findRestaurant(list1 []string, list2 []string) []string {
    pos := make(map[string]int, len(list1))
    for i, s := range list1 {
        pos[s] = i
    }

    best := int(^uint(0) >> 1)
    ans := make([]string, 0)

    for j, s := range list2 {
        if i, ok := pos[s]; ok {
            sum := i + j
            if sum < best {
                best = sum
                ans = ans[:0]
                ans = append(ans, s)
            } else if sum == best {
                ans = append(ans, s)
            }
        }
    }
    return ans
}

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> pos;
        for (int i = 0; i < (int)list1.size(); ++i) {
            pos[list1[i]] = i;
        }

        int best = INT_MAX;
        vector<string> ans;

        for (int j = 0; j < (int)list2.size(); ++j) {
            auto it = pos.find(list2[j]);
            if (it == pos.end()) continue;
            int sum = it->second + j;
            if (sum < best) {
                best = sum;
                ans.clear();
                ans.push_back(list2[j]);
            } else if (sum == best) {
                ans.push_back(list2[j]);
            }
        }

        return ans;
    }
};

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        pos = {name: i for i, name in enumerate(list1)}
        best = float('inf')
        ans = []

        for j, name in enumerate(list2):
            if name not in pos:
                continue
            s = pos[name] + j
            if s < best:
                best = s
                ans = [name]
            elif s == best:
                ans.append(name)

        return ans

var findRestaurant = function(list1, list2) {
  const pos = new Map();
  for (let i = 0; i < list1.length; i++) {
    pos.set(list1[i], i);
  }

  let best = Infinity;
  const ans = [];

  for (let j = 0; j < list2.length; j++) {
    if (!pos.has(list2[j])) continue;
    const s = pos.get(list2[j]) + j;
    if (s < best) {
      best = s;
      ans.length = 0;
      ans.push(list2[j]);
    } else if (s === best) {
      ans.push(list2[j]);
    }
  }

  return ans;
};