Can Make Arithmetic Progression · Optimal Solution

Sort once. Check every gap.

A calibration system expects sensor readings at evenly spaced intervals — 10, 20, 30, 40 — but network latency scrambles the arrival order. Can these values be rearranged into a sequence with a constant step? Sort them to expose the only candidate order, then verify that every adjacent gap matches the first. If any gap deviates, no rearrangement can help. O(n log n) time for the sort. O(1) extra space if sorted in place.

Interactive

Watch the gaps align — or break

Concept

One sort, one contract, one scan

An arithmetic progression has exactly one correct order. Sorting reveals it. The first adjacent gap becomes a contract that every subsequent gap must honor.

sort reveals order

If any permutation of the values forms an arithmetic progression, the sorted order must be that progression. No other arrangement needs checking.

first gap defines the contract

The difference between the first two sorted values sets the expected step. Every subsequent pair must produce exactly this difference.

one mismatch suffices

A single pair with a different gap proves impossibility. The scan can terminate early — no later pair can repair the broken contract.

Algorithm

Sort, establish, verify

The algorithm sorts once, locks in a difference, and verifies it across all adjacent pairs.

  1. 1

    Sort the array

    Sort the values in ascending order. This is the only candidate arrangement for an arithmetic progression.

  2. 2

    Establish the expected difference

    Compute d = sorted[1] − sorted[0]. This is the gap every adjacent pair must replicate.

  3. 3

    Verify remaining pairs

    For each pair (sorted[i−1], sorted[i]) starting at i = 2: if the gap differs from d, return false.

  4. 4

    All gaps matched

    If the scan completes without a mismatch, return true — the values form an arithmetic progression.

Edge Cases

Where the gap check is trivial

Some inputs resolve immediately, exposing the boundaries of the algorithm.

All equal values

When every element is the same, the expected difference is zero. Every gap is zero. The sequence is a valid arithmetic progression with step 0.

Two elements

With only two values, there is exactly one gap — and it defines the difference. No further pairs to check. Every two-element array is trivially arithmetic.

Scrambled input

The input order is irrelevant. The algorithm sorts first, so [16, 4, 10, 7, 1] and [1, 4, 7, 10, 16] produce the same sorted sequence and the same answer.