What if we don't sort the queries?
Intuition (Preprocessing)\nLet\'s preprocess the arrays before looking at the queries:\n\nWe find all the possible sums and keep them sorted. For each sum, we k
# Intuition (Preprocessing)\nLet\'s preprocess the arrays before looking at the queries:\n\nWe find all the possible sums and keep them sorted. For each sum, we keep the `num1`s that made that `sum` in the sorted order as well.\n\n\n# Example (Preprocessing)\n\n\n\nLet\'s consider the first example of the question: \n`nums1 = [4,3,1,2]` \nand \n`nums2 = [2,4,9,5]`\n\nThe sum will be:\n\n`sum = [6, 7, 10, 7]`\n\n\nThis is what our TreeMap `sumToSortedNum1s` will look like after preprocessing:\n\n`sumToSortedNum1s =`\n`{6->{4} , 7-> {2,3}, 10->{1}}`\n\n**Note:** Don\'t worry if you don\'t know what TreeMap is. I\'ll explain in the **Data Structure** Section.\n\nEach `sum` has a list or set of sorted `num1`s which we call it `sortedNum1s`. If it doesn\'t confuse you, we call the whole thing `sumToSortedNum1s` which in Java is a TreeMap.\n\nIn case you are not clear on how the TreeMap is created, index 0 in `nums1` which is 4 contributed to making `sum=6` so `sortedNum1s` for `6` will be `4` which makes `6->{4}`. Index 1 and 3 in nums1 (which have the value of 3 and 2), contributed to creating the sum of 7. So `sortedNum1s` for 7 will be `{2,3}` which makes: `7->{2,3}`.\n\n\n# Intuition (Processing each query)\n\nThen we can look at each query: we are looking for the max sum that satisfies the condition for each query. So we check if the biggest sum satisfies the condition. If yes, we return that sum happily; otherwise, we check the lower sum. \n\nBut how do we check if that sum satisfies the condition?\n\n\n\n# Approach\nFor each sum, we stored all the `num1s` which created that `sum` in the corresponding set or list for that `sum` and call it `sortedNum1s`.  We find the smallest `num1` in `sortedNum1s` for that `sum` which is greater than or equal to `x` (`query[0] = x`).  If such an element exists, then there\'s some hope that it is the ideal match. Now we should look at the other condition. We extract `num2 = sum - num1`. Then check the other condition `num2 >= y` and as you know: `y=query[1]`. If that\'s the case, we cheer loudly and return the winner: `sum`.\n\nOtherwise, we will not look at other `num1`s in the `sortedNum1s` for that `sum` anymore. **Why not?**\n\nSince we found the smallest possible `num1` that satisfied the condition (`num1>=x`), it is guaranteed that our `num2` is maximized. So if our `num2` doesn\'t satisfy the condition (`num2>=y`), then we don\'t waste more time digging into other elements of that `sortedNum1s`, and instead spend the saved time having fun at the beach.\n\n\n\n\n# Data Structure\n\nTreeSet is a set (similar to HashSet) that all elements are sorted. So finding an element in TreeSet takes `O(log n)`. Surprise! Surprise: In Java, TreeSet is Called TreeSet. \n\nTreeMap is similar to a Map (HashMap or HashTable), but the keys are sorted. so given a key, you can find its value in `O(log n)`. You won\'t be able to guess what TreeMap is called in Java.\n\nSo this is what we have:\n`TreeMap<Integer, TreeSet<Integer>>`\n\n\nIf your programming language doesn\'t have a data structure similar to TreeMap, you can implement it yourself by creating a class that has one integer (`sum`) and one sorted list of `num1`s called `sortedNum1s`. Then you can keep those objects in a list sorted by `sum`. However, in that case, I strongly recommend yelling at the people who created your programming language for not implementing TreeMap and starting to write code in Java to give them a lesson.\n\n\n# Complexity\n\n##### Time complexity (Preprocessing):\n\nFor the preprocessing (creating the TreeMap), it takes us `n` times to go through the `nums1` and `nums2` arrays. Since each sum is generated based on adding one index in `num1` and `num2`, the length of `sum` will be at most `n`. In that case, we need `log n` to insert the new sum into the sorted sum map (or list depending on the implementation). But that\'s not all: for that `sum`, we also need to insert `num1` into its `sortedNum1s` list (`TreeSet` in Java) which will take another `log n`. So the preprocessing will be: `O(n * log n * log n)`.\n\n##### Time complexity (Checking each query):\n\nThen for each query, in the worst case, we\'ll look at all `n` elements in the sum, and for each sum, we find the `num1` in the sorted array that can have at most `n` elements, so the time complexity will be `O(q * n * log n)` .\n\n### Advanced Time complexity (do **NOT** read):\n\n**Warning:** You might become more confused! \n\nIf you mention the above time complexity in the interview, it will be good enough to pass the interview for senior software engineering positions: we have `n` sum and for each sum, we have a sorted list of `num1`s which has at most `n` elements. So for each query, the time complexity will be `O(n * log n)` in the worst case. Right?\n\n**Super Short Answer**: Nope!\n\n**Short Answer**: Each element in `nums1` will contribute to creating only one `sum`, and the same `num1` with the same index in `nums1` will not appear in more than one `sum`. So even in the worst case, the total length of all `sortedNum1s` in all `sum`s will be at most `n` elements; So the time complexity for each query will be `O(n)` **not** `O(n * log n)`. \nMore accurately, if the number of the distinct `sum` is `m`, the average length of each `sortedNum1s` in each `sum` will be `d=n/m`  so the time complexity will be `O(m log d)`.\n\n**Long Answer**: Let\'s assume our `nums1` input is `nums1={1,2,3,4}`. \n\n1) First, let\'s try to change `nums2` so that the number of distinct elements in the `sum` is maximized. It\'s not that hard: for example, we can have `nums2={10,10,10,10}` which makes `sum={11,12,13,14}` and the TreeMap will be: `sumToNum1={11->{1} , 12->{2} , 13->{3} , 14->{4}}`. But as you can see, there\'s only one element for each `sortedNum1s` in each `sum` that contributed to making that `sum`. Can you come up with another `nums2` in which `sum` has `n` element and one of the `sortedNum1s` has more than one `num1`? Hell no!In this case, `m == n` and we check all `m` elements in the sum. So the time complexity will be `O(n)`.\n\n\n2) Now let\'s try to maximize the size of a `sortedNum1s` for one specific `sum`. What should the input array `nums2` look like so that for `nums1={1,2,3,4}`, the `sortedNum1s` for `sum=15` is maximized?\nYes, you are correct: `nums2={14,13,12,11}`. Now try to make another sum other than `15` out of `nums1` and `nums2`... \nTry harder ... Nice try! But as you see, there will be only that one sum with `n` elements. The `sum` will be: `{15}` and the TreeMap will be: `{15->{1,2,3,4}}}`. \nIn this case `m==1` and `d==n` so the time complexity will be `O(m log d) = O(1 * log n) = O(log n)` \n\n\n\n\n\n\n\n##### Space complexity:\n`O(n^2)`\n\n### **Advanced** Space complexity:\n`O(n)`\n\n# The Most Difficult Challenge in History\n\nNow here\'s the question for you: Is the time complexity of preprocessing actually `O(n * log n * log n)`? \nPlease comment below for a chance to win a BMW.\nNote: As mentioned in the Terms and Conditions, the chance of winning a BMW is less than `0.000000000000000000000001%`. \nGood luck.\n\n\n# Shout-out:\n\nA special thanks to @DCXiaoBing for their suggestions.\n\n\n# Code\n```   \npublic int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {\n    int[] result = new int[queries.length];\n    TreeMap<Integer, TreeSet<Integer>> sumToSortedNum1 = createTreeMap(nums1, nums2);\n    for (int i = 0; i < result.length; i++) {\n        result[i] = getMax(sumToSortedNum1, queries[i]);\n    }\n    return result;\n}\n\nprivate TreeMap<Integer, TreeSet<Integer>> createTreeMap(int[] nums1, int[] nums2) {\n    TreeMap<Integer, TreeSet<Integer>> sumToSortedNum1 = new TreeMap<>();\n    for (int i = 0; i < nums1.length; i++) {\n        int num1 = nums1[i];\n        int num2 = nums2[i];\n        int sum = num1 + num2;\n        if (!sumToSortedNum1.containsKey(sum)) {\n            sumToSortedNum1.put(sum, new TreeSet<>());\n        }\n        sumToSortedNum1.get(sum).add(num1);\n    }\n    return sumToSortedNum1;\n}\n\nprivate int getMax(TreeMap<Integer, TreeSet<Integer>> sumToSortedNum1, int[] query) {\n    int x = query[0];\n    int y = query[1];\n    Integer sum = sumToSortedNum1.lastKey();\n    while (sum != null && sum >= x + y) {\n        TreeSet<Integer> sortedNum1s = sumToSortedNum1.get(sum);\n        Integer num1 = sortedNum1s.ceiling(x);\n        if (num1 != null && num1 >= x) {\n            int num2 = sum - num1;\n            if (num2 >= y) {\n                return sum;\n            }\n        }\n        sum = sumToSortedNum1.lowerKey(sum);\n    }\n    return -1;\n}\n```
['Java']