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


  • 0
    class Solution {
        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
    D

    Nice optimization!


Log in to reply
 

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