1855. Maximum Distance Between a Pair of Values

two pointers

T: O(n)
S: O(1)

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        
        int max = 0;
        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            
            if (nums1[i] > nums2[j]) { 
                i++;
            } else {
                max = Math.max(max, j - i);
                j++;
            }
            
        }
        return max;
    }
}

/*
is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i

Input: nums1 = 

 0   1.2 3 4
[55,30,5,4,2]
       i       
i <= j
  0. 1. 2. 3. 4
[100,20,10,10,5]
              j       

, nums2 = 
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).

should ignore the example, because what we want is max diff pair


ex: 

desc, so the first one is the biggest, so just move j

[5,4,3,2,1]
 i

[100, 100, 100, 100, 100]
  j

this ex, j can move until end, nums1[j] are all bigger than nums1[i]

so make the j larger, the diff is larger

T: O(n)
S: O(1)
*/

binary search

T: O(nlogn)

S: O(1)

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int max = 0;
        for (int i = 0; i < nums1.length; i++) {
            int idx = bs(nums2, nums1[i]);
            if (idx != -1) {
                max = Math.max(max, idx - i);
            }
        }
        return max;
    }
    private int bs(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left + 1 < right) {
            int mid = left + (right - left)/2;
            if (nums[mid] >= k) { // because nums2 is desc sort, 所以越往右越小, 所以這題要反過來寫
                left = mid; 
            } else {
                right = mid;
            }
        }
        if (nums[right] >= k) { // 選遠的 idx 優先
            return right;
        }
        if (nums[left] >= k) {
            return left;
        }
        return -1;
    }
}