Minimum Index Sum of Two Lists


  • 0

    Click here to see the full article post


  • 0

    Share my Swift solution - O(max(m, n)) time and O(max(m, n)) space using HashMap

    class Solution599 {
        func findRestaurant(_ list1: [String], _ list2: [String]) -> [String] {
            if list1.count == 0 || list2.count == 0 {
                return []
            }
            
            var map = [String: Int]()
            var minSum = Int.max
            var result = [String]()
            
            for i in 0..<list1.count {
                map[list1[i]] = i
            }
            for i in 0..<list2.count {
                if let item = map[list2[i]] {
                    let indexSum = i + item
                    if indexSum < minSum {
                        minSum = min(minSum, indexSum)
                        result.removeAll()
                        result.append(list2[i])
                    } else if indexSum == minSum {
                        result.append(list2[i])
                    }
                }
            }
            
            return result
        }
    }
    

  • 0

    @cloud.runner Thanks for sharing your solution. For now I have added the code. Soon I will add the explanation and animation.


  • 0

    Share My Simpler Solution.

    public static String[] findRestaurant(String[] list1, String[] list2) {
    Map<String, Integer> map1 = new HashMap<>();
    Map<String, Integer> map2 = new HashMap<>();
    Map<Integer, List<String>> result = new TreeMap<>();

        for (int i = 0; i < list1.length; i++) {
            map1.put(list1[i], i);
        }
    
        for (int i = 0; i < list2.length; i++) {
            map2.put(list2[i], i);
        }
    
        for (String key : map1.keySet()) {
            if (map2.containsKey(key)) {
                int sum = map1.get(key) + map2.get(key);
                if (!result.containsKey(sum)) {
                    result.put(sum, new ArrayList<String>() {{
                        add(key);
                    }});
                } else {
                    result.get(sum).add(key);
                }
            }
        }
    
        Map.Entry<Integer, List<String>> entry = result.entrySet().iterator().next();
    
        return entry.getValue().toArray(new String[entry.getValue().size()]);
    }

  • 0
    public static String[] findRestaurant2(String[] list1, String[] list2) {
            Map<String, Integer> map1 = new HashMap<>();
            Map<String, Integer> map2 = new HashMap<>();
            Map<Integer, List<String>> result = new TreeMap<>();
    
            for (int i = 0; i < list1.length; i++) {
                map1.put(list1[i], i);
            }
    
            for (int i = 0; i < list2.length; i++) {
                map2.put(list2[i], i);
            }
    
            for (String key : map1.keySet()) {
                if (map2.containsKey(key)) {
                    int sum = map1.get(key) + map2.get(key);
                    if (!result.containsKey(sum)) {
                        result.put(sum, new ArrayList<String>() {{
                            add(key);
                        }});
                    } else {
                        result.get(sum).add(key);
                    }
                }
            }
    
            Map.Entry<Integer, List<String>> entry = result.entrySet().iterator().next();
    
            return entry.getValue().toArray(new String[entry.getValue().size()]);
        }
    

  • 0
    A

    System.out.println(findRestaurant(new String[]{"Shogun","Tapioca Express","Burger King","KFC"}, new String[]{"KNN","KFC","Burger King","Tapioca Express","Shogun"}));
    failed with 3rd solution.


  • 0

    @acarora According to me 3rd solution is giving right answer for your test case. How it is failing?


  • 0
    A

    @vinod23 yes it worked but i had kinda similar solution and was failing on that test case. but minor changes made it work. sorry for the confusion.


  • 0

    @Vinod23 @compton_scatter We can make it more better.

    While iterating over through List2 if i'th index is greater than minSum than we can simply break the loop


  • 0

    @ruchit_tushar Thanks for your suggestion. I have updated the code.


  • 0
    T

    @ruchit_tushar agree.
    Through all the solutions, it either creates a map for whole list1 or list2.
    However, if the two lists are:
    (A G B E C) and (B E X Y Z)

    You'll soon find 'B' is the answer with minimum index sum 2;
    You don't need to traverse either one of the whole list and make a hash.

    @vinod23 as well.

    Share my ruby solution(although it looks like duplicate, could be simper, but I think it beats all the creating Hash with a whole list solution)

    The basic idea is to keep two indexes to track both list1 and list2; the index limitation could change if we get one index sum for one same pair of strings.

    def find_restaurant(list1, list2)
      min_index_sum = nil
      restaurants = []
      choices_hash = {}
    
      limit1, limit2 = list1.length - 1, list2.length - 1
      index1, index2 = 0, 0
    
      while index1 <= limit1 || index2 <= limit2
        if index1 <= limit1
          if choices_hash.has_key?(list1[index1])
            val = choices_hash[list1[index1]] + index1
            choices_hash[list1[index1]] = val
    
            if min_index_sum.nil? || min_index_sum > val
              min_index_sum = val
              restaurants = [list1[index1]]
            elsif min_index_sum == val
              restaurants << list1[index1]
            end
    
            limit1 = min_index_sum if limit1 > min_index_sum
            limit2 = min_index_sum if limit2 > min_index_sum
          else
            choices_hash[list1[index1]] = index1
          end
    
          index1 += 1
        end
    
        if index2 <= limit2
          if choices_hash.has_key?(list2[index2])
            val = choices_hash[list2[index2]] + index2
            choices_hash[list2[index2]] = val
    
            if min_index_sum.nil? || min_index_sum > val
              min_index_sum = val
              restaurants = [list2[index2]]
            elsif min_index_sum == val
              restaurants << list2[index2]
            end
    
            limit1 = min_index_sum if limit1 > min_index_sum
            limit2 = min_index_sum if limit2 > min_index_sum
          else
            choices_hash[list2[index2]] = index2
          end
    
          index2 += 1
        end
      end
    
      restaurants
    end
    

  • 0
    V

    How about this solution ?
    class Solution(object):
    def findRestaurant(self, list1, list2):
    dict = {}
    list = []
    element = 0
    minsum = 2147483647
    for i in range(0,len(list2)):
    if list2[i] not in dict:
    dict[list2[i]] = i

        for i in range(0,len(list1)):
            if list1[i] in dict:
                tempsum = i + dict[list1[i]]
                if minsum > tempsum:
                    minsum = tempsum
                    element = i
                    if len(list) is not 0:
                        list.pop()
                    list.append(list1[element])
                elif minsum == tempsum:
                    element = i
                    list.append(list1[element])  
        return list

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.