Simple Solution (Only Hash Tables and Sorting) Beats 86% of Solutions in Speed in Four Steps
Approach\n1) We should create two hash tables to collect the maximum num2 for each unique num1 and the maximum num1 for each unique num2.\n2) We fill or overwri
# Approach\n1) We should create two hash tables to collect the maximum num2 for each unique num1 and the maximum num1 for each unique num2.\n2) We fill or overwrite the values only if the new value is greater. This means we keep unique num1 values with their corresponding maximum num2 in maxNum2ForNums1, and unique num2 values with their corresponding maximum num1 in maxNum1ForNums2.\n3) We create a vector from the smaller hash table and sort it in decreasing order based on the maximum value, which can be obtained by adding num1 and num2, the pair now represents the previous values of nums1 and nums2 from the unordered_map.\n4) We search for the maximum sum for the coordinates specified in the queries. Since our vector is already sorted in decreasing order, we minimize the time spent searching. We use a variable found to track whether a value has been found. If no value is found by the end of the loop, we add -1 to the results.\n\n \n\n# Code\n```cpp []\nclass Solution {\npublic:\n    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {\n        int n = nums1.size();\n        unordered_map<int, int> maxNum2ForNums1;\n        unordered_map<int, int> maxNum1ForNums2;\n        vector<int> ans;\n\n        for (int i = 0; i < n; i++) {\n            if (nums2[i] > maxNum2ForNums1[nums1[i]]) {\n                maxNum2ForNums1[nums1[i]] = nums2[i];\n            }\n            if (nums1[i] > maxNum1ForNums2[nums2[i]]) {\n                maxNum1ForNums2[nums2[i]] = nums1[i];\n            }\n        }\n\n        vector<pair<int, pair<int, int>>> sortedPairs;\n        if (maxNum2ForNums1.size() < maxNum1ForNums2.size()) {\n            for (const auto& entry : maxNum2ForNums1) {\n                sortedPairs.emplace_back(entry.first + entry.second, make_pair(entry.first, entry.second));\n            }\n        }\n        else {\n            for (const auto& entry : maxNum1ForNums2) {\n                sortedPairs.emplace_back(entry.first + entry.second, make_pair(entry.second, entry.first));\n            }\n        }\n\n        sort(sortedPairs.rbegin(), sortedPairs.rend());\n\n        for (auto& query : queries) {\n            bool found = false;\n            for (const auto&[maxSum, pairNums] : sortedPairs) {\n                if (pairNums.first >= query[0] && pairNums.second >= query[1]) {\n                    ans.push_back(maxSum);\n                    found = true;\n                    break;\n                }\n            }\n            if (!found) ans.push_back(-1);\n        }\n        return ans;\n    }\n};\n```
['Hash Table', 'Sorting', 'C++']