Minimum Index Sum of Two Lists"
Asked 3 months ago
0Comments
0 Views
The "Minimum Index Sum of Two Lists" problem asks us to:
- Find common strings between two lists of strings.
- For each common string, calculate the sum of its indices in both lists.
- Return the common string(s) with the minimum index sum.
What We Need to Find: We need to return a vector of strings containing all common strings with the least index sum.
Approach and Intuition:
- Use a hash map to store strings from the first list with their indices.
- Iterate through the second list, checking for common strings.
- Keep track of the minimum index sum and update the result accordingly.
Let's break down the solution into more understandable blocks:
#include <vector>
#include <string>
#include <unordered_map>
#include <climits>
#include <iostream>
using namespace std;
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
vector<string> result;
unordered_map<string, int> indexMap;
int minIndexSum = INT_MAX;
// Step 1: Create a map of strings from list1 to their indices
for (int i = 0; i < list1.size(); i++) {
indexMap[list1[i]] = i;
}
// Step 2: Check list2 for common strings and calculate index sums
for (int j = 0; j < list2.size(); j++) {
if (indexMap.count(list2[j]) > 0) {
int currentIndexSum = j + indexMap[list2[j]];
if (currentIndexSum < minIndexSum) {
// New minimum found, clear previous results
minIndexSum = currentIndexSum;
result.clear();
result.push_back(list2[j]);
} else if (currentIndexSum == minIndexSum) {
// Another string with the same minimum index sum
result.push_back(list2[j]);
}
}
}
return result;
}
};
int main() {
Solution solution;
vector<string> list1 = {"Shogun", "Tapioca ", "Burger King", "KFC"};
vector<string> list2 = {"Piatti", "The Grill ", "Hungry ", "Shogun"};
vector<string> result = solution.findRestaurant(list1, list2);
cout << "Result: ";
for (const string& s : result) {
cout << s << " ";
}
cout << endl;
return 0;
}This solution is efficient because:
- It uses a hash map for quick lookups.
- It only iterates through each list once.
- It handles all cases in a single pass through
list2.
The time complexity is O(n + m), where n and m are the lengths of list1 and list2 respectively. The space complexity is O(n) for the hash map.
This approach elegantly solves the problem by keeping track of the minimum index sum while processing the lists, avoiding the need for sorting or multiple passes through the data.
Share