0319EasyArraySorting

Even-Spaced Survey Marks

Tracked in this browser only

Trains the technique from

LeetCode 1502Can Make Arithmetic Progression From Sequence

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A survey crew has a bag of elevation marks, marks, each one a whole number of centimetres relative to the site datum, so a mark below the datum is negative. The marks come out of the bag in no particular order.

The crew wants to know whether the marks can be laid out in some order so that the gap between each mark and the next one is the same all the way along. The shared gap may be positive, negative or zero.

Return true if such an order exists and false otherwise.

Examples

Example 1

Input: marks = [12, 4, 8, 0]
Output: true

Laid out as 0, 4, 8, 12 the gap is 4 every time.

Example 2

Input: marks = [-6, -1, 4, 8]
Output: false

There is no order of -6, -1, 4 and 8 whose gaps are all the same.

Example 3

Input: marks = [-10, 5, -25, 20]
Output: true

Laid out as -25, -10, 5, 20 the gap is 15 every time.

Example 4

Input: marks = [7, 7, 7]
Output: true

Three identical marks sit at a gap of 0 from each other.

Example 5

Input: marks = [3, 3, 6]
Output: false

No order of 3, 3 and 6 has a single shared gap.

Constraints

2 <= marks.length <= 1000
-10^6 <= marks[i] <= 10^6

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def can_space_evenly(marks: list[int]) -> bool:

Java

public boolean canSpaceEvenly(int[] marks)

The intended approach

Time O(n log n)Space O(n) for the sorted copy

If an even spacing exists at all, sorting the marks produces it, since a run with one shared gap is monotonic. Sort a copy, take the gap between the first two marks, and walk the rest checking every neighbouring gap against it.

Pythonentry point: can_space_evenly

def can_space_evenly(marks):
    # O(n log n) time for the sort, then one linear scan.
    # O(n) space, which is the sorted copy of the marks.
    ordered = sorted(marks)
    gap = ordered[1] - ordered[0]
    for i in range(2, len(ordered)):
        if ordered[i] - ordered[i - 1] != gap:
            return False
    return True

The obvious version

Derive the only gap that could work from the smallest and largest mark, then check that the bag holds exactly the marks that spacing demands.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_can_space_evenly(marks):
    n = len(marks)
    lo = min(marks)
    hi = max(marks)
    if lo == hi:
        return True
    span = hi - lo
    if span % (n - 1) != 0:
        return False
    step = span // (n - 1)
    wanted = set()
    for i in range(n):
        wanted.add(lo + i * step)
    if len(set(marks)) != n:
        return False
    return set(marks) == wanted

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in