Python - O(N^2) ➜ O(NLogN) ➜ O(N) | EXPLAINED
1. BRUTE FORCE - O(N^2) - TLE\n\nThe Brute Force approach is pretty simple. For each element, go through each element in second list that is greater or equal an
# **1. BRUTE FORCE - O(N^2) - TLE**\n\nThe Brute Force approach is pretty simple. For each element, go through each element in second list that is greater or equal and keep calculating the maxDistance. Not efficient and will give TLE for large arrays. But from this, we can start thinking about optimizing our solution.\n\n```\ndef maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n        # In Brute force approach, for each element in nums2\n        # we go through each less or equal element in nums2\n        # And we keep track of the maximum distance\n        \n        maxDistanceSoFar = 0\n        \n        for i,num1 in enumerate(nums1):\n            for j in range(i, len(nums2)):\n                if num1 <= nums2[j]: maxDistanceSoFar = max(maxDistanceSoFar, j - i) \n                else: break\n        \n        return maxDistanceSoFar\n```\n\n# **2. BINARY SEARCH - O(NLogN)**\n\nBecause it is given that both the arrays are sorted in decreasing order, it means, instead of linear search on second array, we can perform Binary search. \n\t\n\tWhat do we have to search?\n\n\tWe have to search for the maximum possible value of "j" such that \n\tthe element at "j" index is >= particular element in the first list\n\t\nIf the element at mid satisfies the condition, it might be a possible solution but it is also possible that we may find an element after it that also satisfies the condition. In that case, we will get a larger distance. Hence, even if mid satisfies the condition, we continue searching on right side of mid.\n\t\n\tdef maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n        # Because we are given that both arrays are sorted in decreasing order\n        # We can use Binary search instead of linear search in the inner loop\n        \n        maxDistanceSoFar = 0\n        \n        for i,num1 in enumerate(nums1):\n            # Binary search for the maximum index on right of i index at which element is >= num1\n            start = i\n            end = len(nums2) - 1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                # If mid element is greater than num1, that\'s one possible solution\n                # But we want to maximize the distance\n                if nums2[mid] >= num1:\n                    maxDistanceSoFar = max(maxDistanceSoFar, mid - i)\n                    start = mid + 1\n                else: end = mid - 1\n                    \n        return maxDistanceSoFar\n\t\t\n# **3. TWO POINTERS - O(N)**\n\nUsing Two Pointers approach, we can do this problem in an O(N) time complexity which means this is the fastest solution among the three. \n\nWe start with both the pointers at the beginning of both lists as i <= j\n\nAnd now, we will compare the elements and check whether num2[j] >= num1[i]. If yes, calculate the distance and update the maxDistance if this distance is bigger than previous. And also, since we are looking for the maximum possible distance, we will also increment j. \n\nBut if num2[j] < num1[i], that means not only this element does not satisfy the condition, but no element after it will satisfy because array is sorted in decreasing order. Hence, it means we are done with nums1[i] and so, we can move on to the next ith index element.\n\n\tExample - nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]\n\t\n\tInitially, i = 0, j = 0, maxDistance = 0\n\t\n\tSo, we see that num1[i] = 55 and num2[j] = 100\n\t\n\tSince 100 >= 50. We calculate the distance and it comes out to be 0 since j - i => 0 - 0 => 0\n\t\n\tSince we want to maximize the distance, we increment j. \n\t\n\tNow, i = 0, j = 1, num1[i] = 55 and num2[j] = 20\n\t\n\tIs 20 >= 55? NO! It means, no element after it is valid as well. So, for 55, we are done. Increment i.\n\t\n\tNow, i = 1, j = 1, num1[i] = 30 and num2[j] = 20\n\t\n\tIs 20 >= 30? NO. Again, increment i.\n\t\n\tWe see that here, i = 2 and j = 1. This violates the condition that says i <= j. \n\t\n\tHence, to make sure this condition is not violated, if i becomes > j when we increment it, we will also increment j.\n\t\n\tAnd this process continues till =>  i <len(nums1) and j < len(nums2\n\t\n**HERE IS THE CODE -**\n\n    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:\n        # Since both arrays are sorted in non-decreasing order\n        # We can try two pointer approach here\n        \n        i = 0\n        j = 0\n        maxDistance = 0\n        \n        while i < len(nums1) and j < len(nums2):   \n            # If nums2[j] >= nums1[i] that means it is one possible solution\n            # But because we want to maximize the distance, we increment j\n            # Because if next element also satisfies this condition, then it will have a larger distance\n            if nums2[j] >= nums1[i]: \n                maxDistance = max(maxDistance, j - i)\n                j += 1\n            \n            else: \n                i += 1\n                # We also want to make sure i is <= j\n                if i > j: j += 1\n                \n        return maxDistance
['Two Pointers', 'Binary Search', 'Binary Tree', 'Python']