Minimum Index Sum of Two Lists - Practice Coding Problems

Minimum Index Sum of Two Lists - Problem

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Input & Output

Example 1 — Basic Case

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

› Output: ["Shogun"]

💡 Note: "Shogun" appears at index 0 in list1 and index 3 in list2, giving sum 0+3=3. This is the only common string with the minimum index sum.

Example 2 — Multiple Results

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

› Output: ["Shogun","KFC"]

💡 Note: "Shogun" has sum 0+1=1, "KFC" has sum 3+0=3, "Burger King" has sum 2+2=4. "Shogun" has minimum sum, but wait - "KFC" has sum 3, not 1. Actually "Shogun" sum is 0+1=1, "KFC" sum is 3+0=3, "Burger King" sum is 2+2=4. Only "Shogun" has minimum sum 1.

Example 3 — Single Match

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

› Output: ["sad","happy","good"]

💡 Note: "happy": 0+1=1, "sad": 1+0=1, "good": 2+2=4. Both "sad" and "happy" have minimum sum 1.

Constraints

1 ≤ list1.length, list2.length ≤ 1000
1 ≤ list1[i].length, list2[i].length ≤ 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.

Visualization

Tap to expand

Understanding the Visualization

Input Lists

Two arrays of restaurant preferences in order

Find Common

Identify strings that appear in both lists

Calculate Sums

Add position indices for each common string

Minimum Sum

Return all strings with the smallest index sum

Key Takeaway

🎯 Key Insight: Use hash map to efficiently find common strings and track minimum index sum in one pass

Asked in

Y Yelp 15 a Amazon 12 G Google 8 f Facebook 6

The key insight is to use a hash map to store the indices of strings from the first list, then iterate through the second list to find common strings and track the minimum index sum. The optimal hash map approach runs in O(n+m) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n×m)	O(k)	Compare every string in list1 with every string in list2
Hash Map Optimization	O(n+m)	O(n)	Use hash map to store indices from first list, then check second list

Brute Force — Algorithm Steps

Compare each string in list1 with all strings in list2
Record all common strings and their index sums
Find minimum index sum among all common strings
Return all strings with the minimum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Pairs

Check every list1[i] with list2[j]

Track Minimum

Find common strings with smallest i+j sum

Result

Return all strings with minimum index sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

char** solution(char** list1, int list1Size, char** list2, int list2Size, int* returnSize) {
    char** commonStrings = malloc(1000 * sizeof(char*));
    int count = 0;
    int minSum = INT_MAX;
    
    // Find all common strings and their index sums
    for (int i = 0; i < list1Size; i++) {
        for (int j = 0; j < list2Size; j++) {
            if (strcmp(list1[i], list2[j]) == 0) {
                int indexSum = i + j;
                if (indexSum < minSum) {
                    minSum = indexSum;
                    count = 0;
                    commonStrings[count++] = list1[i];
                } else if (indexSum == minSum) {
                    commonStrings[count++] = list1[i];
                }
            }
        }
    }
    
    *returnSize = count;
    return commonStrings;
}

int main() {
    // Implementation for parsing input and calling solution
    // Print result in JSON array format
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

Nested loops: n strings in list1 × m strings in list2 for comparisons

✓ Linear Growth

Space Complexity

O(k)

Only store result list with k common strings

✓ Linear Space

89.0K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler