A regional radio network has installed n broadcast towers on a flat coordinate plane, each at integer coordinates (x, y). To reduce interference, engineers want the widest possible north-south buffer corridor — a vertical strip of some width w, lying between the leftmost and rightmost towers — that contains no tower strictly inside it (a tower may sit exactly on either edge of the strip). Two or more towers may share the same coordinates. Given the tower positions, find the maximum possible width w of such a corridor.
Print a single integer: the maximum width of a vertical corridor, lying between the leftmost and rightmost tower, that contains no tower strictly inside it.
Example 1
Input
5 8 7 9 9 7 4 9 7 4 3
Expected
3
Explanation
Sorting the tower x-coordinates gives 4, 7, 8, 9, 9. The widest gap between consecutive values is between 4 and 7 (a corridor of width 3); no tower's x-coordinate falls strictly inside that strip even though towers exist further right, so the answer is 3.
Example 2
Input
2 3 1 9 0
Expected
6
Explanation
With only two towers, the entire span between them (from x=3 to x=9) is empty by definition, giving a corridor width of 6.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →