Minimum Index Sum of Two Lists

easy

Last Updated - 10/09/2024

Problem Statement Solution 1: Set Difference and Index Calculation Solution 2: Index Mapping and Sorting Solution 3: Double Loop Comparison with Minimum Sum Calculation Solution 4: Double Loop with Minimum Index Sum Tracking Solution 5: Set Intersection and Index Sum Calculation Solution 6: Double Loop with Index Sum Comparison Solution 7: Index Tracking and Sum Mapping More Problems Solutions

Problem Statement

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.

Example 1

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"] , list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]

Output: ["Shogun"]

Example 2

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"] , list2 = ["KFC","Shogun","Burger King"]

Output: ["Shogun"]

Example 3

Input: list1 = ["happy","sad","good"] , list2 = ["sad","happy","good"]

Output: ["happy","sad"]

Constraints

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.

Solution 1: Set Difference and Index Calculation

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"]

Solution 2: Index Mapping and Sorting

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"]

Solution 3: Double Loop Comparison with Minimum Sum Calculation

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"]

Solution 4: Double Loop with Minimum Index Sum Tracking

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"]

Solution 5: Set Intersection and Index Sum Calculation

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"]

Solution 6: Double Loop with Index Sum Comparison

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"]

Solution 7: Index Tracking and Sum Mapping

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"]