Problem

Given two arrays. Find the smallest difference between two elements from both of the arrays.

Examples

Example 1:

1
2
3

Input: nums1 = [1, 3, 15, 11, 2], nums2 = [23, 127, 235, 19, 8]
Output: 3
Explanation: The smallest difference is between 11 (from nums1) and 8 (from nums2), i.e., |11 - 8| = 3.

Example 2:

1
2
3

Input: nums1 = [10, 5, 40], nums2 = [50, 90, 80]
Output: 10
Explanation: The smallest difference is between 40 (from nums1) and 50 (from nums2), i.e., |40 - 50| = 10.

Solution

Method 1 - Brute Force

It’ll be O(n*m) as we need to iterate the 2nd list for each element of 1st list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

 public class Solution {
 
     public int[] smallestDifference(int[] nums1, int[] nums2) {
         double minDifference = Double.MAX_VALUE;
         int[] resultPair = new int[2];
 
         // Iterate through each pair of elements from both arrays
         for (int element1 : nums1) {
             for (int element2 : nums2) {
                 int currentDifference = Math.abs(element1 - element2);
                 if (currentDifference < minDifference) {
                     minDifference = currentDifference;
                     resultPair[0] = element1;
                     resultPair[1] = element2;
                 }
             }
         }
 
         return resultPair;
     }
 
     public static void main(String[] args) {
         Solution solution = new Solution();
         int[] nums1 = {1, 3, 15, 11, 2};
         int[] nums2 = {23, 127, 235, 19, 8};
         int[] pair = solution.smallestDifference(nums1, nums2);
         System.out.println("Pair with smallest difference: [" + pair[0] + ", " + pair[1] + "]");
     }
 }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def smallest_difference(nums1, nums2):
    min_difference = float("inf")
    result_pair = (None, None)

    # Iterate through each pair of elements from both arrays
    for element1 in nums1:
        for element2 in nums2:
            current_difference = abs(element1 - element2)
            if current_difference < min_difference:
                min_difference = current_difference
                result_pair = (element1, element2)

    return result_pair


# Example usage
nums1 = [1, 3, 15, 11, 2]
nums2 = [23, 127, 235, 19, 8]
print(f"Pair with smallest difference: {smallest_difference(nums1, nums2)}")

Complexity

  • ⏰ Time complexity: O(m*n), where m is the length of nums1 and n is the length of nums2.
  • 🧺 Space complexity: O(1)

Method 2 - Sorting and Using Two-pointers

Notice that consecutive elements in a sorted array will have the smallest difference when compared to non-consecutive pairs. Therefore, to find the pair with the smallest difference in a single array, sort the array first and then check the difference between each consecutive pair of elements.

For example, after sorting [1, 3, 15, 11, 2] , the pairs (1,2) and (2, 3) have the smallest difference.

To find the smallest difference between two arrays, we can extend this approach as follows:

  1. Sort both arrays using sorting algorithm with O(n log n) complexity, where n is the size of the larger array.
  2. Use two pointers to traverse the starts of the sorted arrays.
  3. Calculate the difference between elements pointed to by these pointers. If this is smaller than the current minimum difference, update the minimum difference and the corresponding pair of elements.
  4. Move the pointer in the array that has the smaller element to the right. Since the arrays are sorted, moving the smaller element pointer can potentially yield a pair with a smaller difference.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class Solution {
    // Function to find the pair with the smallest difference between two
    // elements from two arrays
    public int[] findSmallestDifferencePair(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0, j = 0;
        int minDiff = Integer.MAX_VALUE;
        int[] pair = new int[2];

        while (i < nums1.length && j < nums2.length) {
            int diff = Math.abs(nums1[i] - nums2[j]);
            if (diff < minDiff) {
                minDiff = diff;
                pair[0] = nums1[i];
                pair[1] = nums2[j];
            }

            if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }

        return pair;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def findSmallestDifferencePair(nums1, nums2):
    nums1.sort()
    nums2.sort()

    i, j = 0, 0
    min_diff = float("inf")
    pair = (None, None)

    while i < len(nums1) and j < len(nums2):
        diff = abs(nums1[i] - nums2[j])
        if diff < min_diff:
            min_diff = diff
            pair = (nums1[i], nums2[j])

        if nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1

    return pair

Complexity

  • ⏰ Time complexity: O(m log m + n log n)
  • 🧺 Space complexity: O(1)