Clear Explanation of O(nlogn) algorithm
Let\'s start selecting j index from the end of nums2 array, because our solution must satisfy the condition i < j. So it is more intuitive to select as large as
Let\'s start selecting `j` index from the end of `nums2` array, because our solution must satisfy the condition `i < j`. So it is more intuitive to select as large as possible `j` index and do the logic after that. As for `i` index, we must find the minimum `i` in `nums1` array, such that `nums1[i] <= nums2[j]`.\nNotice that both array are non-increasing (`arr` is non-increasing if `arr[i-1] >= arr[i]` for every `1 <= i < arr.length`), so they are decrease ordered. Thus we can use **binary search algorithm** to find `i` in `nums1` array.\n\nWhen we find appropriate `i` in `nums1` array, we must consider the difference `(j - i)` and compare it to previous difference value to select **max** between them. There is exist legitimate question: why we don\'t break finding process at this point? Why do we consider other pairs of indices `(i, j)`? Because it may happen that `nums2[j-k]` (where `k` is `0 <= k < j <= nums2.length`) would be too greater than `nums[j]`. So `i` index would be near of `0` index in `nums1` array. The example is:\n`nums1 = [20, 10, 6, 4, 2]`   `nums2 = [80, 70, 60, 50, 5]`    so when `j = 4 nums2[4] = 5`  and `i = 3  nums1[3] = 4`.  So `(j - i) = 4 - 3 = 1` but `j = 3 nums2[3] = 50` and `i = 0  nums1[0] = 30, (j - i) = 3`.   Thus we would have found more valid pair `(j, i)` and its difference is `3`.\n\nProcess that is described above is main part of solution, but let\'s consider **edge cases**.\n 1. `elem` from `nums2` array is the smallest one in `nums1` array. So there is not exist `i` in `nums1` array. Then the difference `(j - i)` doesn\'t exist also.\n 2. `elem` from `nums2` array is the greatest one in `nums1` array, then `i` index must be `0`.\n 3. `nums1` and `nums2` arrays lengthes **are not equal** each other. Our algorithm must consider this edge case.\n\nSo there is java code:\n\n```java\npublic int maxDistance(int[] nums1, int[] nums2) {\n        int res = 0;\n        int start = 0, end = nums1.length - 1;\n        for (int j = nums2.length - 1; j >= 0; j--) {\n            int i = findAppropIndex(nums1, start, end, nums2[j]);\n\n            if (i > end) continue;\n\n            int diff = j - i;\n            res = Math.max(res, diff);\n            end = Math.min(j, i);\n        }\n        return res;\n    }\n\n    private int findAppropIndex(int[] arr, int start, int end, int elem) {\n        if (elem < arr[end]) { // arr: [10, 9, 8, 7, 7]  elem:  5\n            return end + 1;\n        }\n        int low = start, high = end;\n        while (low < high) {\n            int mid = low + (high - low) / 2;\n            if (arr[mid] > elem) {\n                low = mid + 1;\n            } else {\n                high = mid;\n            }\n        }\n        return high;\n    }\n```\n\n***Notice:***\n\n**Binary search:**  In general, it is better to compute mid as `low + (high - low) / 2` than  `(low + high) / 2`, because `(low + high)` may be bigger than integer type capacity.\n\n**end = Math.min(j, i):**  This is for better performance. We should not start to find `i` index always in the same range from `nums1` array. The range should be from `0` to `Math.min(j, i)`. We must select minimum value from `(j, i)` and do not assign `j` or `i` directly to the `end` variable (like: `end = j` or `end = i`). Because if we write `end = i`, what happens if `nums2.length` is smaller than `nums1.length`? Index `j` may be smaller than index `i`, so if `j < i` we could not have a valid pair even than `nums1[i] <= nums2[j]`. Second condition also must be satisfied: i <= j. And what happens if `end = j`? It may be **ArrayIndexOutOfBoundsException** when we select `arr[mid]` in binary search function. Because `mid = low + (high - low) / 2`. So if `nums2.length > nums1.length` mid index may be greater than `nums1.length` also. Thus we need minimum value from `j` and `i`.\n\nTime complexity is `O(nlogm)` where `m` is `nums1` array length and `n` is `nums2` array length. Ordering of `nums2` array is` O(n)` and in each step we do `O(logm)` operation for binary search in `nums1` array.\n\nI would love to have some sort of feedback from you. If you share me what can be improved in the article and what problems do you see currently, I\'ll correct them.\nThanks for reading.
['Binary Tree', 'Java']