Widest Gap in Sorted Order

HardArrays & Hashing

Problem

A seismograph records event times in times, unsorted. The analysts want the longest quiet period: the largest difference between two consecutive values once the times are sorted.

Return that difference, or 0 if there are fewer than two times. Your solution must run in linear time and space.

Example 1

Input:
times = [3, 6, 9, 1]
Output:
3

Sorted: 1, 3, 6, 9; the gaps are 2, 3, 3.

Example 2

Input:
times = [10]
Output:
0

Example 3

Input:
times = [1, 10000000]
Output:
9999999

Constraints

  • 1 ≤ times.length ≤ 10^5
  • 0 ≤ times[i] ≤ 10^9
  • O(n) time.

Hint

Show the first hint

Sorting costs O(n log n). Can you prove where the largest gap cannot be?

Walkthrough

How to approach it

01Clarify before coding

  • Can values repeat? Yes; a gap of 0 is possible.
  • Fewer than two values? Return 0.
  • Is sorting allowed? It gives the right answer, but the requirement is linear time.

02Brute force

Sort, then scan consecutive differences.

Cost: O(n log n) time: correct but misses the linear-time requirement.

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.