Minimum Index Sum of Two Lists

🏠 ⬅️ ➡️

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.

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.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    use, intrinsic :: iso_fortran_env, only : error_unit, output_unit
    implicit none
    character(len=:), allocatable :: list1(:), list2(:)
    integer :: i, j, k, n, m
    type(string_set) :: common_strings

    call get_command_argument(1, n)
    allocate(list1(n))
    do i = 1, n
        call get_command_argument(i+1, list1(i))
    end do

    call get_command_argument(2, m)
    allocate(list2(m))
    do j = 1, m
        call get_command_argument(j+1+n, list2(j))
    end do

    common_strings = get_common_strings(list1, list2)

    write (output_unit, '(*(g0,:," ",a))') common_strings%strings

contains

    function get_common_strings(list1, list2) result(common_strings)
        implicit none
        character(len=*), intent(in) :: list1(:), list2(:)
        type(string_set) :: common_strings
        integer :: i, j

        common_strings = string_set()

        do i = 1, size(list1)
            do j = 1, size(list2)
                if (list1(i) == list2(j)) then
                    call common_strings%add(list1(i))
                end if
            end do
        end do

    end function get_common_strings

    type :: string_set
        class(*), pointer :: strings(:) => null()
    contains
        procedure :: add => add_string
        generic :: assignment(=) => add
    end type string_set

    subroutine add_string(self, string)
        implicit none
        class(string_set), intent(inout) :: self
        character(len=*), intent(in) :: string
        integer :: i

        if (.not. associated(self%strings)) then
            allocate(self%strings(1))
            self%strings(1) = string
        else
            do i = 1, size(self%strings)
                if (self%strings(i) == string) return
            end do
            allocate(self%strings(size(self%strings)+1))
            self%strings(size(self%strings)) = string
        end if

    end subroutine add_string

end program main
❌ Compiled
❌ Executed
❌ Correct 
module common_strings

implicit none

contains

subroutine solve(list1, list2, common_strings)

! This subroutine takes two arrays of strings list1 and list2, and returns
! all the common strings with the least index sum.

! list1: array of strings
! list2: array of strings
! common_strings: array of strings

character(len=*), intent(in) :: list1(:)
character(len=*), intent(in) :: list2(:)
character(len=*), intent(out) :: common_strings(:)

! Local variables
integer :: i, j, k, l, m, n, o
integer :: index_sum
logical :: found

! Initialize the common strings array
common_strings = ""

! Loop through the elements of list1
do i = 1, size(list1)

    ! Loop through the elements of list2
    do j = 1, size(list2)

        ! Check if the current element of list1 is in list2
        if (index(list2(j), list1(i)) /= 0) then

            ! If it is, add it to the common strings array
            common_strings = [common_strings, list1(i)]

            ! Check if the current element of list2 is in list1
            if (index(list1(i), list2(j)) /= 0) then

                ! If it is, add it to the common strings array
                common_strings = [common_strings, list2(j)]

            end if

        end if

    end do

end do

! Sort the common strings array in ascending order
call sort(common_strings)

! Print the common strings
do i = 1, size(common_strings)
    write (*,*) common_strings(i)
end do

end subroutine solve

end module common_strings

program main

use common_strings

implicit none

! Test case 1
character(len=*), parameter :: list1(4) = ["Shogun ", "Tapioca Express ", "Burger King ", "KFC "]
character(len=*), parameter :: list2(4) = ["Piatti ", "The Grill at Torrey Pines ", "Hungry Hunter Steakhouse ", "Shogun "]

call solve(list1, list2, common_strings)

! Test case 2
character(len=*), parameter :: list1(4) = ["Shogun ", "Tapioca Express ", "Burger King ", "KFC "]
character(len=*), parameter :: list2(4) = ["KFC ", "Shogun ", "Burger King "]

call solve(list1, list2, common_strings)

! Test case 3
character(len=*), parameter :: list1(3) = ["happy ", "sad ", "good "]
character(len=*), parameter :: list2(3) = ["sad ", "happy ", "good "]

call solve(list1, list2, common_strings)

end program main
🌐 Data from online sources 
from typing import List

def findRestaurant(list1: List[str], list2: List[str]) -> List[str]:
    restaurantMap = {restaurant: i for i, restaurant in enumerate(list1)}

    minSum = float("inf")
    result = []
    for j, restaurant in enumerate(list2):
        if restaurant in restaurantMap:
            totalSum = j + restaurantMap[restaurant]
            if totalSum < minSum:
                result = [restaurant]
                minSum = totalSum
            elif totalSum == minSum:
                result.append(restaurant)

    return result

1. Create a hashmap to store the restaurants and their indices (or just index for Python and JavaScript) in list1.
  1. Initialize a variable, minSum, to store the minimum sum of indices, and a result list to store the common restaurants with the least index sum.
  2. Iterate through list2; for each restaurant, check if it is in the hashmap. a. If it is, calculate the sum of its index in list1 and list2. b. If the sum is less than the current minSum, clear the result list, add the current restaurant to the result list, and update minSum. c. If the sum is equal to minSum, add the restaurant to the result list.
  3. Return the result list.
🌐 Data from online sources 
#include <vector>
#include <unordered_map>
#include <string>

std::vector<std::string> findRestaurant(std::vector<std::string>& list1, std::vector<std::string>& list2) {
    std::unordered_map<std::string, int> restaurantMap;
    for (int i = 0; i < list1.size(); i++) {
        restaurantMap[list1[i]] = i;
    }

    int minSum = INT_MAX;
    std::vector<std::string> result;
    for (int j = 0; j < list2.size(); j++) {
        if (restaurantMap.count(list2[j])) {
            int sum = j + restaurantMap[list2[j]];
            if (sum < minSum) {
                result.clear();
                result.push_back(list2[j]);
                minSum = sum;
            } else if (sum == minSum) {
                result.push_back(list2[j]);
            }
        }
    }
    return result;
}

1. Create a hashmap to store the restaurants and their indices (or just index for Python and JavaScript) in list1.
  1. Initialize a variable, minSum, to store the minimum sum of indices, and a result list to store the common restaurants with the least index sum.
  2. Iterate through list2; for each restaurant, check if it is in the hashmap. a. If it is, calculate the sum of its index in list1 and list2. b. If the sum is less than the current minSum, clear the result list, add the current restaurant to the result list, and update minSum. c. If the sum is equal to minSum, add the restaurant to the result list.
  3. Return the result list.