End Stones Close Ranks

Medium

Stones lie on a number line at distinct integer points; their coordinates are in the array spots. An end stone is one with the smallest or the largest coordinate. In one move you take an end stone and put it on a free integer point so that it **stops** being an end stone. For example, with stones at 1, 2 and 5, the stone at 5 cannot be moved: wherever it goes, it remains an end stone. The game ends when all the stones occupy consecutive points. Return a list of two numbers: the fewest and the most moves the game can take.

Example 1

spots=[3, 8, 4] → [2, 3]

The stone at 8 cannot go to 5, since it would still be an end stone. So the minimum is two moves, e.g. 3→6 and then 8→5. The maximum is three: 3→5, 4→6, 5→7.

Example 2

spots=[10, 11, 13, 12] → [0, 0]

The stones already sit side by side, so the game is over before it starts.

Example 3

spots=[1, 2, 3, 4, 20, 21] → [2, 15]

Constraints

3 ≤ len(spots) ≤ 10⁴
1 ≤ spots[i] ≤ 10⁹
All coordinates are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Two Pointers Sorting

Similar problems

Sorted Parabola Values Medium Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Four Numbers to a Target Medium Flags in Three Colors Medium

Input

spots=[3, 8, 4]

Expected

[2, 3]

Run checks the first 3 tests in your browser. Submit checks all 140 tests on the server, hidden ones included.