Minimum Index Sum of Two Lists

Problem Statement

Given two distinct lists of strings list1 and list2, the task is to identify strings that appear in both lists and amongst those, determine those that have the smallest sum of their indices in their respective lists. This value, the index sum, is calculated by adding the position of the string in list1 to its position in list2. The solution should include all strings that are found in both lists and tie for the smallest index sum. The output does not require a specific order for the result strings.

Examples

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 string is "Shogun".

Example 2

Input:

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

Output:

["Shogun"]

Explanation:

The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.

Example 3

Input:

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

Output:

["sad","happy"]

Explanation:

There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".

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.
• There is at least a common string between list1 and list2.

Approach and Intuition

The challenge involves two main tasks:

1. Identifying strings that are common in both lists.
2. Among the common strings, determining those that have the smallest index-sum (sum of the positions in their respective lists).

• First, one intuitive approach is to utilize a hash map to keep track of each string's index in one list. This aids in quick lookup when iterating through the second list to find common strings.

• For every string that is found in both lists:

  • Compute the index sum.
  • If it's the smallest encountered so far, update the smallest sum and reset the list of results.
  • If it matches the current smallest sum, add it to the list of results.

• Processing power and memory are both utilized efficiently with hash maps, especially considering the constraints of a maximum of 1000 elements per list and maximum string length of 30.

The approach's efficiency comes from avoiding a direct O(n*m) complexity you would get from directly comparing each element of one list to every element of another, by utilizing memory to store and quickly lookup index information. Given the constraints, the use of additional memory in this way is acceptable and indeed optimal for this problem. This method ensures that each list is iterated over at most once or twice, thus making the time complexity effectively O(n + m), where n and m are the lengths of list1 and list2 respectively.

Solutions

public class Solution {
    public String[] commonFavorites(String[] favorites1, String[] favorites2) {
        HashMap<String, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < favorites1.length; i++)
            indexMap.put(favorites1[i], i);
        List<String> result = new ArrayList<>();
        int leastIndexSum = Integer.MAX_VALUE, currentSum;
        for (int j = 0; j < favorites2.length && j <= leastIndexSum; j++) {
            if (indexMap.containsKey(favorites2[j])) {
                currentSum = j + indexMap.get(favorites2[j]);
                if (currentSum < leastIndexSum) {
                    result.clear();
                    result.add(favorites2[j]);
                    leastIndexSum = currentSum;
                } else if (currentSum == leastIndexSum)
                    result.add(favorites2[j]);
            }
        }
        return result.toArray(new String[result.size()]);
    }
}