Java Solution with 1 HashMap and explanation


  • 0
    N
    public String[] findRestaurant (String[] list1, String[] list2)
    {
    	String[] shorterList, longerList;
    	shorterList = list1.length > list2.length ? list2 : list1;
    	longerList = list1.length > list2.length ? list1 : list2;
    	int minIndexSum = Integer.MAX_VALUE;
    
    	List<String> commonList = new ArrayList<String>();
    	Map<String, Integer> hm = new HashMap<>();
    
    	for (int i = 0; i < shorterList.length; i++)
    	{
    		hm.put(shorterList[i], i);
    	}
    
    	for (int i = 0; i < longerList.length; i++)
    	{
    		if (hm.containsKey(longerList[i]))
    		{
    			int sum = i + hm.get(longerList[i]);
    			if (sum < minIndexSum)
    			{
    				minIndexSum = sum;
    				commonList.clear();
    				commonList.add(longerList[i]);
    			}
    			else if (sum == minIndexSum)
    			{
    				commonList.add(longerList[i]);
    			}
    		}
    	}
    
    	return commonList.toArray(new String[0]);
    }
    

    It is given that there will always be one answer. Thus, I find out shorter list and insert those elements in HashMap along with their index, as answer will most definitely be from that list.

    Then, iterate through longer list, and if a common restaurant is found, calculate index sum. If it is less than current lowest, then need to clear ArrayList and add element with new lowest. If it is equal to current lowest, then add it to ArrayList. Finally, return the ArrayList as a String array.


Log in to reply
 

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