0750MediumArrayEnumeration

Longest Evenly Spaced Stretch After One Re-cut

Tracked in this browser only

Trains the technique from

LeetCode 3872Longest Arithmetic Sequence After Changing At Most One Element

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 driven markers along a rail line and written down readings, where readings[i] is the distance recorded at marker i, in order along the line.

A stretch is a block of markers at consecutive positions of readings. A stretch is evenly spaced when the difference between each pair of neighbouring readings inside it is the same throughout. A stretch of one or two markers is evenly spaced, since it has no pair of differences to disagree.

Before measuring, the crew may re-cut at most one marker: choose at most one index of readings and replace its reading with any integer you like, which may be negative and may repeat another reading. Only one index may be replaced in total.

Return the number of markers in the longest evenly spaced stretch that exists after the re-cut.

Examples

Example 1

Input: readings = [3, 6, 9, 20, 15, 18]
Output: 6

Re-cut marker 3 to 12. The readings become 3, 6, 9, 12, 15, 18, where every neighbouring pair differs by 3, so all six markers sit in one evenly spaced stretch.

Example 2

Input: readings = [1, 5, 2, 9]
Output: 3

Re-cut marker 2 to 9. Markers 0, 1 and 2 then read 1, 5, 9, a stretch of three whose neighbouring readings differ by 4 throughout.

Example 3

Input: readings = [50, 1, 4, 7, 10]
Output: 5

Re-cut marker 0 to -2. The readings become -2, 1, 4, 7, 10, spaced 3 apart the whole way, so the stretch covers all five markers. A replacement reading is allowed to be negative.

Constraints

4 <= readings.length <= 10^5
1 <= readings[i] <= 10^5
The replacement reading may be any integer, and is not restricted to the range above.

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 longest_even_stretch(readings: list[int]) -> int:

Java

public int longestEvenStretch(int[] readings)

The intended approach

Time O(n) for n markers: two run-length passes and two linear enumerations.Space O(n) for the gap list and the two run tables.

Turn the readings into the list of gaps between neighbouring markers, so an evenly spaced stretch of `k` markers is a block of `k - 1` equal gaps. Re-cutting one marker rewrites only the gaps touching it: an end marker of the stretch touches one gap, which becomes free to be anything, while an inner marker touches two neighbouring gaps whose sum stays fixed, so they can both be set to `d` only when that sum is exactly `2 * d`. Precompute, for every gap position, how far a block of equal gaps runs back to it and how far one runs forward from it, using two linear passes. Then enumerate the four shapes a best stretch can take: an untouched block of equal gaps; a block with one free gap added at its left or at its right; and a rewritten neighbouring pair with a block of equal gaps on its left, on its right, or on both, accepted only when the pair's sum is twice that block's gap. Three markers are always achievable by re-cutting an outer one, which seeds the answer.

Pythonentry point: longest_even_stretch

def longest_even_stretch(readings):
    # Work on the gaps between neighbouring markers. Re-cutting one marker
    # rewrites at most two neighbouring gaps and cannot change their sum, so the
    # answer is found by enumerating where those rewritten gaps sit.
    # O(n) time, O(n) space.
    n = len(readings)
    m = n - 1
    gap = [readings[i + 1] - readings[i] for i in range(m)]

    run_to = [1] * m           # equal gaps ending at i
    for i in range(1, m):
        run_to[i] = run_to[i - 1] + 1 if gap[i] == gap[i - 1] else 1
    run_from = [1] * m         # equal gaps starting at i
    for i in range(m - 2, -1, -1):
        run_from[i] = run_from[i + 1] + 1 if gap[i] == gap[i + 1] else 1

    # three markers can always be settled by re-cutting one of the outer two
    best = 3
    for i in range(m):
        # no re-cut needed at all
        if run_to[i] + 1 > best:
            best = run_to[i] + 1
        # re-cut the marker on the left edge of the stretch: gap i is free
        if i + 1 < m and run_from[i + 1] + 2 > best:
            best = run_from[i + 1] + 2
        # re-cut the marker on the right edge of the stretch: gap i is free
        if i - 1 >= 0 and run_to[i - 1] + 2 > best:
            best = run_to[i - 1] + 2

    # re-cut a marker strictly inside the stretch: gaps i - 1 and i are rewritten
    for i in range(1, m):
        total = gap[i - 1] + gap[i]
        left = i - 2 >= 0
        right = i + 1 < m
        if left and right and gap[i - 2] == gap[i + 1] and total == 2 * gap[i - 2]:
            cand = run_to[i - 2] + run_from[i + 1] + 3
            if cand > best:
                best = cand
        if left and total == 2 * gap[i - 2]:
            cand = run_to[i - 2] + 3
            if cand > best:
                best = cand
        if right and total == 2 * gap[i + 1]:
            cand = run_from[i + 1] + 3
            if cand > best:
                best = cand
    return best

The obvious version

For every stretch and every marker in it, drop the differences that marker touches, check that the surviving differences agree on one spacing, and check that the marker can actually be given a reading that produces that spacing. Report the longest stretch that passes. Quartic in the number of markers.

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_longest_even_stretch(readings):
    """Test every stretch against every choice of which marker to re-cut, working
    straight from the definition."""
    n = len(readings)

    def settles(lo, hi):
        gaps = [readings[j + 1] - readings[j] for j in range(lo, hi)]
        if len(set(gaps)) <= 1:
            return True
        for k in range(lo, hi + 1):
            rest = [readings[j + 1] - readings[j]
                    for j in range(lo, hi) if j != k - 1 and j != k]
            if len(set(rest)) > 1:
                continue
            if rest:
                d = rest[0]
                if lo < k < hi:
                    if readings[k + 1] - readings[k - 1] == 2 * d:
                        return True
                else:
                    return True
            else:
                if lo < k < hi:
                    if (readings[k + 1] - readings[k - 1]) % 2 == 0:
                        return True
                else:
                    return True
        return False

    best = 1
    for lo in range(n):
        for hi in range(lo, n):
            if hi - lo + 1 > best and settles(lo, hi):
                best = hi - lo + 1
    return best

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
3 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