public class Solution { //time complexity: O(n) //space complexity: O(1) public static int biggestDiffPair(int[] a, int[] b) { int minAIndex = -1; int minBIndex = -1; int maxAIndex = -1; int maxBIndex = -1; for (int i = 0; i < a.length; i++) { if (minAIndex == -1 || a[i] < a[minAIndex]){ minAIndex = i; } if (maxAIndex == -1 || a[i] > a[maxAIndex]){ maxAIndex = i; } } for (int i = 0; i < b.length; i++) { if (minBIndex == -1 || b[i] < b[minBIndex]){ minBIndex = i; } if (maxBIndex == -1 || b[i] > b[maxBIndex]){ maxBIndex = i; } } if (a[maxAIndex] - b[minBIndex] > b[maxBIndex] - a[minAIndex]){ System.out.println(b[minBIndex] + "---" + a[maxAIndex]); return a[maxAIndex] - b[minBIndex]; } System.out.println(a[minAIndex] + "---" + b[maxBIndex]); return b[maxBIndex] - a[minAIndex]; } //time complexity: O(nlogn) //space complexity: O(logn) public static int smallestDiffPair(int[] a, int[] b) { quickSort(a); quickSort(b); int indexA = 0; int indexB = 0; int minDiff = Math.abs(a[0]-b[0]); int diffIndexA = 0; int diffIndexB = 0; //running on both arrays simultaneously, from smallest, striving for minimal diff while (indexA < a.length && indexB < b.length) { int diff = Math.abs(a[indexA] - b[indexB]); if (diff < minDiff){ minDiff = diff; diffIndexA = indexA; diffIndexB = indexB; } if (diff > 0) {//a[indexA] > b[indexB] -> increasing indexB //we want to decrease the difference, in order for it to find the minimum, // so we increase the lower number in from current indexes in both arrays indexA++; } else { indexB++; } } System.out.println(Math.min(a[diffIndexA], b[diffIndexB]) + "---" + Math.max(a[diffIndexA], b[diffIndexB])); return minDiff; } //לא נדרש לממש, מספיק להפנות לעמוד הרלוונטי בחוברת שקפים private static void quickSort(int[] arr) { quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int start, int end) { if (start < end) { int partitionIndex = partition(arr, start, end); quickSort(arr, start, partitionIndex - 1); quickSort(arr, partitionIndex + 1, end); } } private static int partition(int[] arr, int start, int end) { int pivot = arr[end]; int i = (start - 1); for (int j = start; j < end; j++) { if (arr[j] <= pivot) { i++; swap(arr, i, j); } } swap(arr, i + 1, end); return i + 1; } private static void swap(int[] arr, int index1, int index2) { int temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp; } }