algoadvance

Leetcode 599. Minimum Index Sum of Two Lists

Problem Statement

The problem is as follows:

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 common restaurant is "Shogun" with index sum 0 (3 + 0).

Example 2:

Input: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant that has the least index sum is "Shogun" with index sum 1 (0 + 1).

Constraints:

Clarifying Questions

  1. Are there any duplicate entries within the individual lists?
    • No, per the problem statement, each list contains unique strings.
  2. How should ties be handled?
    • All answers with the same minimum index sum should be returned.
  3. Should the result be sorted in any particular order?
    • No particular order is required for the result.

Strategy

  1. Build a Hash Map for list1: Create a map where the key is the restaurant name and the value is its index in list1.
  2. Iterate Through list2: For each restaurant in list2, check if it is present in the map created from list1.
  3. Compute Index Sums: Calculate the sum of indices for each common restaurant and keep track of the minimum index sum encountered.
  4. Track Minimum Sums: If a matching restaurant has the current minimum sum, add it to the result. If a lower sum is found, reset the result to include only this new restaurant.
  5. Return the Result: After iterating through list2, return the resultant list of restaurants with the minimum index sum.

Code

Here’s the implementation in C++:

#include <vector>
#include <string>
#include <unordered_map>
#include <climits>

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

        std::vector<std::string> result;
        int minSum = INT_MAX;

        for (int j = 0; j < list2.size(); ++j) {
            if (indexMap.find(list2[j]) != indexMap.end()) {
                int sum = j + indexMap[list2[j]];
                if (sum < minSum) {
                    result.clear();
                    result.push_back(list2[j]);
                    minSum = sum;
                } else if (sum == minSum) {
                    result.push_back(list2[j]);
                }
            }
        }

        return result;
    }
};

Time Complexity

  1. Building the Hash Map: O(n) where n is the length of list1.
  2. Iterating Through list2: O(m) where m is the length of list2.
  3. Overall: Since building the hash map and then iterating through list2 are two separate linear passes, the total time complexity is O(n + m).

This should offer efficient performance for the problem constraints provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI