Intuitive solution. Time O(m+n), Space O(m+n)


  • 0
    M

    Intuitive solution. Time O(m+n), Space O(m+n)

    instead of manipulating the result list, use hashmap to build a list of strings that are in the same distance.
    keep track of the least index sum, and return the list of strings that are mapped from the least index sum.

    public String[] findRestaurant(String[] list1, String[] list2) {
            Map<String, Integer> map = new HashMap<>();
            for(int i = 0; i < list1.length; i++)
                map.put(list1[i], i);
            
            int min = Integer.MAX_VALUE;
            Map<Integer, List<String>> distMap = new HashMap<>();
            for(int i = 0; i < list2.length; i++) {
                String restaurant = list2[i];
                if(map.containsKey(restaurant)) {
                    int dist = Math.abs(i+map.get(restaurant));
                    distMap.putIfAbsent(dist, new ArrayList<String>());
                    distMap.get(dist).add(restaurant);
                    
                    min = Math.min(min, dist);
                }
            }
            
            return distMap.get(min).toArray(new String[0]);
        }
    

Log in to reply
 

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