**π‘ Problem Formulation:** We aim to find the smallest difference between the maximum and minimum values where each value comes from one of three different sorted arrays. Given three lists `l1`

, `l2`

, and `l3`

, the challenge is to find the smallest possible value of `max(a, b, c) - min(a, b, c)`

where `a`

, `b`

, and `c`

are elements from each respective list. The target is to efficiently search through combinations to minimize this difference.

## Method 1: Brute Force Triple Loop

This method involves nested loops to iterate through every combination of elements from the three arrays. It is straightforward but not optimal for large arrays due to its `O(n^3)`

time complexity; however, it guarantees finding the minimum difference.

Here’s an example:

def brute_force_min_diff(l1, l2, l3): min_diff = float('inf') for a in l1: for b in l2: for c in l3: current_diff = max(a, b, c) - min(a, b, c) min_diff = min(min_diff, current_diff) return min_diff # Example arrays l1 = [1, 4, 10] l2 = [2, 15, 20] l3 = [10, 12] # Function call print(brute_force_min_diff(l1, l2, l3))

Output:

5

In this code snippet, the function `brute_force_min_diff()`

computes the minimum difference by examining every combination of elements from the three arrays. Despite its simplicity, the triple loop’s inefficiency means this method is best suited for small datasets.

## Method 2: Two-Pointer Technique

The two-pointer technique optimizes the search using the fact the arrays are sorted. The method maintains a pointer for each array, and only moves the pointer that points to the minimum element at any given time. This reduces the time complexity significantly to `O(n)`

.

Here’s an example:

def two_pointer_min_diff(l1, l2, l3): i, j, k = 0, 0, 0 min_diff = float('inf') while i < len(l1) and j < len(l2) and k < len(l3): a, b, c = l1[i], l2[j], l3[k] current_diff = max(a, b, c) - min(a, b, c) min_diff = min(min_diff, current_diff) if min_diff == 0: break # Move the pointer that points to the smallest element if a == min(a, b, c): i += 1 elif b == min(a, b, c): j += 1 else: k += 1 return min_diff # Function call print(two_pointer_min_diff(l1, l2, l3))

Output:

5

The function `two_pointer_min_diff()`

executes more efficiently by iterating over the arrays in a single pass. By only incrementing the pointer to the smallest element, it narrows the search for the minimum difference without unnecessary checks.

## Method 3: Binary Search Variant

When two arrays are significantly larger than the third, a binary search variant can be employed to find the optimal element in the larger arrays for a given element in the smallest array. While this method may also reach an `O(n log m)`

complexity where `n`

is the size of the smallest array and `m`

the size of the larger, it is a strong contender for asymmetrical data.

Here’s an example:

import bisect def binary_search_min_diff(l1, l2, l3): l1, l2, l3 = sorted((l1,l2,l3), key=len) min_diff = float('inf') for a in l1: idx_b = bisect.bisect_left(l2, a) idx_c = bisect.bisect_left(l3, a) for b in (l2[idx_b-1:idx_b+1] if idx_b else l2[:1]): for c in (l3[idx_c-1:idx_c+1] if idx_c else l3[:1]): current_diff = max(a, b, c) - min(a, b, c) min_diff = min(min_diff, current_diff) return min_diff print(binary_search_min_diff(l1, l2, l3))

Output:

5

The `binary_search_min_diff()`

function employs binary search to find the closest elements to an item from `l1`

in the other two larger arrays. By examining only the nearest candidates, it reduces the number of required calculations.

## Method 4: Heap-Based Multiway Merge

This technique uses a heap to maintain the current set of elements. The idea is to replace the element from the heap that belongs to the same list as the minimum element, moving as a synchronized multiway merge. This is particularly efficient when all arrays are large and equally sized, with a time complexity of `O(n log k)`

, where `k`

is the number of arrays.

Here’s an example:

import heapq def heap_min_diff(l1, l2, l3): min_diff = float('inf') max_val = -float('inf') pq = [] for i, lst in enumerate([l1, l2, l3]): heapq.heappush(pq, (lst[0], i, 0)) max_val = max(max_val, lst[0]) while pq: min_val, list_idx, element_idx = heapq.heappop(pq) current_diff = max_val - min_val min_diff = min(min_diff, current_diff) if element_idx+1 < len([l1, l2, l3][list_idx]): next_val = [l1, l2, l3][list_idx][element_idx+1] heapq.heappush(pq, (next_val, list_idx, element_idx+1)) max_val = max(max_val, next_val) else: break return min_diff print(heap_min_diff(l1, l2, l3))

Output:

5

The `heap_min_diff()`

function provides a clever way to merge inputs while keeping track of the min and max values. By using a heap, it reduces overhead and only explores feasible paths toward the minimal difference.

## Bonus One-Liner Method 5: Pythonic Itertools

Python’s itertools library can create Cartesian products in a concise manner, combined with generator expressions to trim computations. While this might not be the most efficient for large arrays, it’s certainly the most Pythonic and succinct one-liner solution.

Here’s an example:

from itertools import product def pythonic_min_diff(l1, l2, l3): return min(max(comb) - min(comb) for comb in product(l1, l2, l3)) print(pythonic_min_diff(l1, l2, l3))

Output:

5

The function `pythonic_min_diff()`

uses a generator within `min()`

to evaluate the smallest difference from all possible combinations. This one-liner showcases the power of Python’s comprehensions and itertools.

## Summary/Discussion

**Method 1: Brute Force Triple Loop.**The simplest but least efficient with a complexity of`O(n^3)`

. Guaranteed to work but impractical for large datasets.**Method 2: Two-Pointer Technique.**A much more efficient solution with linear complexity`O(n)`

. Optimal for equally sized sorted arrays.**Method 3: Binary Search Variant.**Best suited for datasets where one array is significantly shorter. Its time complexity is of`O(n log m)`

where sizes differ.**Method 4: Heap-Based Multiway Merge.**Utilizes a heap for synchronized merging, with a complexity of`O(n log k)`

it handles large, equally sized arrays well.**Bonus Method 5: Pythonic Itertools.**The most compact and readable method. It leverages`itertools.product`

and is a nice one-liner for smaller datasets.