You are given two lists of strings, list1 and list2. Your task is to find all the common strings between these two lists and return those with the smallest index sum. The index sum for a common string is defined as the sum of its indices in list1 and list2.
To put it simply, you need to find the common strings such that the sum of their positions in both lists is the smallest possible. If multiple strings have the same minimum index sum, return all of them.
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"] , list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"] , list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Input: list1 = ["happy","sad","good"] , list2 = ["sad","happy","good"]
Output: ["happy","sad"]
1 <= list1.length, list2.length <= 1000: Both lists can have up to 1000 strings each.
1 <= list1[i].length, list2[i].length <= 30: Each string in the lists has a length of up to 30 characters.
All strings in list1 and list2 consist of English letters and spaces.
All strings in list1 are unique, and all strings in list2 are unique.
There is at least one common string between list1 and list2.
function findRestaurantUsingSetDifferenceAndIndexCalculation(list1, list2) {
const set1 = new Set(list1);
const set2 = new Set(list2);
const common = [...set1].filter(item => set2.has(item));
const indexSumMap = new Map();
common.forEach(item => {
const indexInList1 = list1.indexOf(item);
const indexInList2 = list2.indexOf(item);
const sum = indexInList1 + indexInList2;
indexSumMap.set(item, sum);
});
let minSum = Infinity;
const result = [];
indexSumMap.forEach((sum, item) => {
if (sum < minSum) {
minSum = sum;
result.length = 0;
result.push(item);
} else if (sum === minSum) {
result.push(item);
}
});
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingSetDifferenceAndIndexCalculation(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingSetDifferenceAndIndexCalculation(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingSetDifferenceAndIndexCalculation(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingIndexMappingAndSorting(list1, list2) {
const indexMap = {};
const combinedList = [];
// Create a map of indices for list2
list2.forEach((item, index) => {
indexMap[item] = index;
});
// Find common items and their index sums
list1.forEach((item, index) => {
if (indexMap.hasOwnProperty(item)) {
combinedList.push([index + indexMap[item], item]);
}
});
// Sort the list by index sum
combinedList.sort((a, b) => a[0] - b[0]);
const result = [];
let minSum = combinedList.length > 0 ? combinedList[0][0] : Infinity;
// Collect all items with the minimum index sum
combinedList.forEach(([sum, item]) => {
if (sum === minSum) {
result.push(item);
} else {
return;
}
});
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingIndexMappingAndSorting(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingIndexMappingAndSorting(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingIndexMappingAndSorting(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingDoubleLoopComparison(list1, list2) {
const result = [];
let minSum = Infinity;
// Iterate through both lists to find common elements and their index sums
for (let i = 0; i < list1.length; i++) {
for (let j = 0; j < list2.length; j++) {
if (list1[i] === list2[j]) {
const sum = i + j;
if (sum < minSum) {
result.length = 0; // Clear the result array
result.push(list1[i]);
minSum = sum;
} else if (sum === minSum) {
result.push(list1[i]);
}
}
}
}
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingDoubleLoopComparison(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingDoubleLoopComparison(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingDoubleLoopComparison(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingDoubleLoopWithIndexSumTracking(list1, list2) {
let minSum = list1.length + list2.length; // Initialize with the maximum possible sum
const result = [];
// Iterate through both lists to find common elements and their index sums
for (let i = 0; i < list1.length; i++) {
for (let j = 0; j < list2.length; j++) {
if (list1[i] === list2[j]) {
const sum = i + j;
if (sum < minSum) {
// New minimum sum found, update result array
result.length = 0;
result.push(list2[j]);
minSum = sum;
} else if (sum === minSum) {
// Same minimum sum, add the element to the result array
result.push(list2[j]);
}
}
}
}
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingDoubleLoopWithIndexSumTracking(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingDoubleLoopWithIndexSumTracking(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingDoubleLoopWithIndexSumTracking(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingSetIntersectionAndIndexSum(list1, list2) {
const set1 = new Set(list1);
const set2 = new Set(list2);
// Find the intersection of both sets to get common elements
const common = [...set1].filter(item => set2.has(item));
const indexSumMap = {};
// Calculate the index sum for each common element
common.forEach(item => {
indexSumMap[item] = list1.indexOf(item) + list2.indexOf(item);
});
// Find the minimum index sum
const minIndexSum = Math.min(...Object.values(indexSumMap));
// Collect all elements with the minimum index sum
const result = [];
for (const [item, sum] of Object.entries(indexSumMap)) {
if (sum === minIndexSum) {
result.push(item);
}
}
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingSetIntersectionAndIndexSum(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingSetIntersectionAndIndexSum(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingSetIntersectionAndIndexSum(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingDoubleLoopAndIndexComparison(list1, list2) {
const result = [];
let minIndexSum = Infinity;
for (let i = 0; i < list1.length; i++) {
const word = list1[i];
if (list2.includes(word)) {
for (let j = 0; j < list2.length; j++) {
const w2 = list2[j];
if (w2 === word) {
const indexSum = i + j;
if (indexSum < minIndexSum) {
result.length = 0; // Clear the result array
result.push(word);
minIndexSum = indexSum;
} else if (indexSum === minIndexSum) {
result.push(word);
}
}
}
}
}
return result;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingDoubleLoopAndIndexComparison(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingDoubleLoopAndIndexComparison(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingDoubleLoopAndIndexComparison(list13,list2 3); //output: ["happy","sad"]
function findRestaurantUsingIndexTrackingAndSumMapping(list1, list2) {
const indexMap = new Map();
const sumMap = new Map();
// Map elements of list1 to their indices
for (let i = 0; i < list1.length; i++) {
indexMap.set(list1[i], i);
}
// Find common elements and map their index sums
for (let i = 0; i < list2.length; i++) {
if (indexMap.has(list2[i])) {
const key = i + indexMap.get(list2[i]);
if (!sumMap.has(key)) {
sumMap.set(key, []);
}
sumMap.get(key).push(list2[i]);
}
}
// Get the list of common strings with the minimum index sum
const minIndexSum = Math.min(...sumMap.keys());
const resultList = sumMap.get(minIndexSum) || [];
return resultList;
}
const list11 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 1 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"];
findRestaurantUsingIndexTrackingAndSumMapping(list11,list2 1); //output: ["Shogun"]
const list12 = ["Shogun","Tapioca Express","Burger King","KFC"];
const list2 2 = ["KFC","Shogun","Burger King"];
findRestaurantUsingIndexTrackingAndSumMapping(list12,list2 2); //output: ["Shogun"]
const list13 = ["happy","sad","good"];
const list2 3 = ["sad","happy","good"];
findRestaurantUsingIndexTrackingAndSumMapping(list13,list2 3); //output: ["happy","sad"]