9-liner C++ O(M+N) time and O(min(M, N)) space with space optimized and early termination


  • 0

    If current index i is already bigger than current min index sum, exit loop right away.

        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            if (list1.size() < list2.size()) return findRestaurant(list2, list1);
            
            // always convert shorter vector to hash map (save space)
            unordered_map<string, int> map2; int i2 = -1;
            for (auto& s : list2) map2[s] = ++i2;
            
            vector<string> res;
            for (size_t i = 0, minSum = INT_MAX; i  < min(minSum+1, list1.size()); ++i) {
                int sum = map2.count(list1[i])? i + map2[list1[i]] : INT_MAX;
                if (sum < minSum) res = {list1[i]}, minSum  = sum;
                else if (sum == minSum) res.push_back(list1[i]);
            }
            return res;
        }
    

Log in to reply
 

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