Closest Across Three Lists

MediumTwo Pointers

Problem

Three teams each submit availability times, sorted in non-decreasing order: a, b and c. A meeting picks one time from each list, and its spread is the latest picked time minus the earliest.

Return the smallest possible spread.

Example 1

Input:
a = [1, 4, 10], b = [2, 15, 20], c = [10, 12]
Output:
5

Pick 10, 15, 10 → spread 15 - 10 = 5.

Example 2

Input:
a = [5], b = [5], c = [5]
Output:
0

Constraints

  • 1 ≤ a.length, b.length, c.length ≤ 10^5
  • -10^9 ≤ values ≤ 10^9
  • Each list is sorted in non-decreasing order

Hint

Show the first hint

For a fixed choice of three values, the spread is max - min. Which pointer move could reduce it?

Walkthrough

How to approach it

01Clarify before coding

  • Exactly one time from each list? Yes.
  • Can lists have different lengths? Yes.
  • Return the spread or the chosen times? The spread.

02Brute force

Try every combination of one value per list.

Cost: O(n · m · p): up to 10^15 combinations.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.